{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum XOR of Two Numbers in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #trie #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字典树 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaximumXOR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中两个数的最大异或值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，返回<em> </em><code>nums[i] XOR nums[j]</code> 的最大运算结果，其中 <code>0 ≤ i ≤ j &lt; n</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,10,5,25,2,8]\n",
    "<strong>输出：</strong>28\n",
    "<strong>解释：</strong>最大运算结果是 5 XOR 25 = 28.</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [14,70,53,83,49,91,36,80,92,51,66,70]\n",
    "<strong>输出：</strong>127\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-xor-of-two-numbers-in-an-array](https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-xor-of-two-numbers-in-an-array](https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,10,5,25,2,8]', '[14,70,53,83,49,91,36,80,92,51,66,70]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def numberToBits ( n, nBits ):\n",
    "  ans = [ 0 ] * nBits\n",
    "\n",
    "  for i in range( len( ans ) ):\n",
    "    ans[ i ] = n & 1\n",
    "    n >>= 1\n",
    "\n",
    "  return tuple( reversed( ans ) )\n",
    "\n",
    "\n",
    "def nBitsRequired ( n ):\n",
    "  if n <= 0:\n",
    "    return 0\n",
    "\n",
    "  nBits = 0\n",
    "  while n != 0:\n",
    "    n >>= 1\n",
    "    nBits += 1\n",
    "\n",
    "  return nBits\n",
    "\n",
    "\n",
    "class TrieNode:\n",
    "  def __init__ ( self ):\n",
    "    self.child = [ None, None ]\n",
    "\n",
    "\n",
    "def trieInsert ( root, bits ):\n",
    "  p = root\n",
    "\n",
    "  for bit in bits:\n",
    "    if p.child[ bit ] == None:\n",
    "      p.child[ bit ] = TrieNode()\n",
    "    p = p.child[ bit ]\n",
    "\n",
    "\n",
    "def findMaxXor ( root, bits ):\n",
    "  p, result = root, 0\n",
    "\n",
    "  for bit in bits:\n",
    "    result *= 2\n",
    "    diff = 1 - bit\n",
    "    if p.child[ diff ] != None:\n",
    "      result += 1\n",
    "      p = p.child[ diff ]\n",
    "    else:\n",
    "      p = p.child[ bit ]\n",
    "\n",
    "  return result\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def findMaximumXOR(self, nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    trieRoot = TrieNode()\n",
    "\n",
    "    nBits = nBitsRequired( max( nums ) )\n",
    "    bits = dict()\n",
    "\n",
    "    for n in nums:\n",
    "      bitsOfN = numberToBits( n, nBits )\n",
    "      bits[ n ] = bitsOfN\n",
    "      trieInsert( trieRoot, bitsOfN )\n",
    "\n",
    "    return max( findMaxXor( trieRoot, bits[ n ] ) for n in nums )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # M1 暴力算法 O(N**2)\n",
    "        # M2 建立前缀树 \n",
    "        \n",
    "        \n",
    "        # M3 按位计算(最高32位 因此时间复杂度O(n))\n",
    "        # 根据异或性质  If a ^ b = c, then a ^ c = b and c ^ b = a\n",
    "        # 最高32位 先看第32位有没有可能是1 再看31位有没有可能 一直到第1位有没有可能\n",
    "        # 判断i位有没有可能是1的方法是 目前从32-i位最大可能是mx 看nums内有没有n1和n2前32-i位异或值位mx\n",
    "        # 也就是 求n1前32-i位与mx的异或值 在不在nums的前32-i位中\n",
    "        \n",
    "        mx = 0\n",
    "        mask = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            possible_mx = mx | 1 << i  # 下一个可能最大值是当前最大值的下一位变成1\n",
    "            mask = mask | 1 << i # mask每次迭代下一位变成1\n",
    "            \n",
    "            s = set()\n",
    "            for num in nums:\n",
    "                s.add(num & mask)\n",
    "            if len(s) <= 1:\n",
    "                continue\n",
    "            for j in s:\n",
    "                if j ^ possible_mx in s:\n",
    "                    mx = possible_mx\n",
    "                    break\n",
    "            \n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        mask = 0 \n",
    "        for i in range(31, -1, -1):\n",
    "            temp = mask | 1 << i\n",
    "            exist = set()\n",
    "            for n in nums:\n",
    "                exist.add(temp & n)\n",
    "            for n in exist:\n",
    "                if n ^ temp in exist:\n",
    "                    mask = temp\n",
    "                    break\n",
    "        return mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Trie:\n",
    "#     def __init__(self, val):\n",
    "#         self.val = val\n",
    "#         self.child = {}\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        \n",
    "#         #取得最大长度\n",
    "#         L = len(format(max(nums), 'b'))-1\n",
    "\n",
    "#         # 构建前缀树\n",
    "#         root = Trie(-1)\n",
    "       \n",
    "#         for n in nums:\n",
    "#             curr = root\n",
    "#             for i in range(L, -1, -1):\n",
    "\n",
    "#                 v = (n >> i) & 1\n",
    "#                 if v not in curr.child:\n",
    "#                     curr.child[v] = Trie(v)\n",
    "\n",
    "#                 curr = curr.child[v]\n",
    "\n",
    "#         res = 0\n",
    "\n",
    "#         #搜索\n",
    "#         for n in nums:\n",
    "#             curr = root\n",
    "#             total = 0\n",
    "#             for i in range(L, -1, -1):\n",
    "#                 v = (n >> i) & 1\n",
    "#                 if 1-v in curr.child:\n",
    "#                     total = total * 2 + 1\n",
    "#                     curr = curr.child[1-v]\n",
    "#                 else:\n",
    "#                     total = total * 2\n",
    "#                     curr = curr.child[v]\n",
    "            \n",
    "#             #print(n, total)\n",
    "#             res = max(res, total)\n",
    "\n",
    "#         return res\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        HIGH_BIT = 30\n",
    "        ans = 0\n",
    "\n",
    "        for k in range(HIGH_BIT, -1, -1):\n",
    "            seen = set(i >> k for i in nums)\n",
    "            ans = ans * 2 + 1\n",
    "            \n",
    "            if all(i ^ ans not in seen for i in seen):\n",
    "                ans -= 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        HIGH_BIT = 30\n",
    "\n",
    "        x = 0\n",
    "        for k in range(HIGH_BIT, -1, -1):\n",
    "            seen = set()\n",
    "            # 将所有的 pre^k(a_j) 放入哈希表中\n",
    "            for num in nums:\n",
    "                # 如果只想保留从最高位开始到第 k 个二进制位为止的部分\n",
    "                # 只需将其右移 k 位\n",
    "                seen.add(num >> k)\n",
    "\n",
    "            # 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分\n",
    "            # 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1\n",
    "            x_next = x * 2 + 1\n",
    "            found = False\n",
    "            \n",
    "            # 枚举 i\n",
    "            for num in nums:\n",
    "                if x_next ^ (num >> k) in seen:\n",
    "                    found = True\n",
    "                    break\n",
    "\n",
    "            if found:\n",
    "                x = x_next\n",
    "            else:\n",
    "                # 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0\n",
    "                # 即为 x = x*2\n",
    "                x = x_next - 1\n",
    "        \n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        now = mask = 0\n",
    "        for i in range(30, -1, -1):\n",
    "            now |= 1 << i\n",
    "            mask |= 1 << i\n",
    "            book = set(num & mask for num in nums)\n",
    "            now ^= next((0 for num in book if now ^ num in book), 1 << i)\n",
    "        return now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        m1 = max(nums).bit_length()\n",
    "        m2 = min(nums).bit_length()\n",
    "\n",
    "        cnt = [0] * 32\n",
    "        \n",
    "        for i in range(32):\n",
    "            for num in nums:\n",
    "                if num & (1 << i):\n",
    "                    cnt[i] += 1\n",
    "\n",
    "        i = 31\n",
    "        while i >= 0:\n",
    "            if 0 < cnt[i] < n:\n",
    "                break\n",
    "            i -= 1\n",
    "\n",
    "        mask = (1 << (i + 1)) - 1\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for num in nums:\n",
    "            idx = bisect_left(nums, mask ^ num)\n",
    "            \n",
    "            if idx < n:\n",
    "                res = max(res, num ^ nums[idx])\n",
    "            if idx > 0:\n",
    "                res = max(res, num ^ nums[idx - 1])\n",
    "            if idx + 1 < n:\n",
    "                res = max(res, num ^ nums[idx + 1])\n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        ans, mask = 0, 0 \n",
    "        high_bit = max(nums).bit_length() - 1\n",
    "        seen = set()\n",
    "        for i in range(high_bit, -1, -1) : \n",
    "            mask |= 1 << i \n",
    "            new_ans = ans | (1 << i)\n",
    "            seen.clear()\n",
    "            for x in nums : \n",
    "                x &= mask \n",
    "                if new_ans ^ x in seen : \n",
    "                    ans = new_ans\n",
    "                    break \n",
    "                seen.add(x) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        mask = 0\n",
    "        res = 0\n",
    "        print(max(nums))\n",
    "        for i in range(32, -1, -1):\n",
    "            mask = mask | 1 << i\n",
    "            print()\n",
    "\n",
    "            pre = set()\n",
    "            for num in nums:\n",
    "                pre.add(mask & num)\n",
    "            \n",
    "            tmp = res | 1 << i\n",
    "            for x in pre:\n",
    "                if x ^ tmp in pre:\n",
    "                    res = tmp\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        O(n^2)会超时\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                nn = nums[j]\n",
    "                print(n, nn, n ^ nn)\n",
    "                ans = max(ans, n ^ nn)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        从高位到低位按位异或, 不断筛选能得到最大值nums\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(zero: List[int], one: List[int], bs) -> int:\n",
    "            if bs < 0:\n",
    "                if not zero or not one:\n",
    "                    # 单个数自己与自己异或结果是0\n",
    "                    return 0\n",
    "\n",
    "                # 从高位到低位按位分化到最后, zero或one中剩下的肯定是同一个数\n",
    "                z = zero[0]\n",
    "                o = one[0]\n",
    "                res = z ^ o\n",
    "                print(\"res\", z ^ o, z, o)\n",
    "                return res\n",
    "\n",
    "            # print(bs, zero, one)\n",
    "            b = 1 << bs\n",
    "            if not zero or not one:\n",
    "                l = zero or one\n",
    "                z = [n for n in l if not n & b]\n",
    "                o = [n for n in l if n & b]\n",
    "                if z and o:\n",
    "                    # 第bs位可以异或得到1\n",
    "                    return dfs(z, o, bs - 1)\n",
    "                else:\n",
    "                    # 第bs位可以异或得到0\n",
    "                    return dfs(l, [], bs - 1)\n",
    "            else:\n",
    "                z1 = [n for n in zero if n & b]  # zero中第bs位是1\n",
    "                o0 = [n for n in one if not n & b]  # one中第bs位是0\n",
    "\n",
    "                z0 = [n for n in zero if not n & b]  # zero中第bs位是0\n",
    "                o1 = [n for n in one if n & b]  # one中第bs位是1\n",
    "\n",
    "                if (z1 and o0) or (z0 and o1):\n",
    "                    # 第bs位可以异或得到1\n",
    "                    # print(\"diff\", bs, z1, o0, z0, o1)\n",
    "                    if (z1 and o0) and (z0 and o1):\n",
    "                        return max(dfs(z1, o0, bs - 1), dfs(z0, o1, bs - 1))\n",
    "                    elif z1 and o0:\n",
    "                        return dfs(z1, o0, bs - 1)\n",
    "                    elif z0 and o1:\n",
    "                        return dfs(z0, o1, bs - 1)\n",
    "                else:\n",
    "                    # 第bs位只能异或得到0\n",
    "                    # print(\"same\", bs, z1, o0, z0, o1)\n",
    "                    return dfs(zero, one, bs - 1)\n",
    "\n",
    "        ans = dfs(nums, [], 31)\n",
    "        return ans\n",
    "\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        从高位到低位按位异或\n",
    "        异或的运算法则: 如果x = a ^ b, 则a = x ^ b\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "\n",
    "        for b in reversed(range(32)):\n",
    "            # 计算所有数的前b位\n",
    "            s = {}\n",
    "            for n in nums:\n",
    "                p = n >> b\n",
    "                s[p] = 1\n",
    "\n",
    "            # 假设ans的第b位可以异或得到1\n",
    "            t = (ans << 1) | 1\n",
    "            for p in s:\n",
    "                if t ^ p in s:  # 哈希表查找元素操作的时间复杂度是O(1)\n",
    "                    # 说明存在某2个数的前b位可以异或得到t\n",
    "                    ans = t\n",
    "                    break\n",
    "            else:\n",
    "                ans <<= 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        O(n^2)会超时\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                nn = nums[j]\n",
    "                print(n, nn, n ^ nn)\n",
    "                ans = max(ans, n ^ nn)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        def dfs(zero: List[int], one: List[int], bs) -> int:\n",
    "            \"\"\"\n",
    "            从高位到低位按位异或, 筛选能得到最大值nums\n",
    "            \"\"\"\n",
    "            if bs < 0:\n",
    "                # 因为按位\n",
    "                res = zero[0] ^ one[0]\n",
    "                print(\"res\", zero[0] ^ one[0], zero[0], one[0])\n",
    "                return res\n",
    "\n",
    "            # print(bs, zero, one)\n",
    "            b = 1 << bs\n",
    "            if not zero or not one:\n",
    "                l = zero or one\n",
    "                if len(l) < 2:\n",
    "                    # 单个数自己与自己异或结果是0\n",
    "                    return 0\n",
    "\n",
    "                z = [n for n in l if not n & b]\n",
    "                o = [n for n in l if n & b]\n",
    "                if z and o:\n",
    "                    # 第bs位可以异或得到1\n",
    "                    return dfs(z, o, bs - 1)\n",
    "                else:\n",
    "                    # 第bs位可以异或得到0\n",
    "                    return dfs(l, [], bs - 1)\n",
    "            else:\n",
    "                z1 = [n for n in zero if n & b]  # 第bs位是1\n",
    "                o0 = [n for n in one if not n & b]  # 第bs位是0\n",
    "\n",
    "                z0 = [n for n in zero if not n & b]  # 第bs位是0\n",
    "                o1 = [n for n in one if n & b]  # 第bs位是1\n",
    "\n",
    "                if (z1 and o0) or (z0 and o1):\n",
    "                    # 第bs位可以异或得到1\n",
    "                    # print(\"diff\", bs, z1, o0, z0, o1)\n",
    "                    if (z1 and o0) and (z0 and o1):\n",
    "                        return max(dfs(z1, o0, bs - 1), dfs(z0, o1, bs - 1))\n",
    "                    elif z1 and o0:\n",
    "                        return dfs(z1, o0, bs - 1)\n",
    "                    elif z0 and o1:\n",
    "                        return dfs(z0, o1, bs - 1)\n",
    "                else:\n",
    "                    # 第bs位只能异或得到0\n",
    "                    # print(\"same\", bs, z1, o0, z0, o1)\n",
    "                    return dfs(zero, one, bs - 1)\n",
    "\n",
    "        ans = dfs(nums, [], 31)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        max_xor = 0\n",
    "        mask = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            mask |= 1 << i\n",
    "            prefixes = {num & mask for num in nums}\n",
    "            temp = max_xor | 1 << i\n",
    "            for prefix in prefixes:\n",
    "                if temp ^ prefix in prefixes:\n",
    "                    max_xor = temp\n",
    "                    break\n",
    "        return max_xor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        # 从最高位开始考虑\n",
    "        for i in range(30, -1, -1):\n",
    "            # 考虑前几位的集合\n",
    "            _set = {(num >> i) for num in nums}\n",
    "            # 期望接下来能取到的最大ans\n",
    "            ans_hope = (ans << 1) + 1\n",
    "            found = False\n",
    "            # 考虑每个集合里的元素，看有没有能满足ans_hope的\n",
    "            for num in _set:\n",
    "                if (ans_hope ^ num) in _set:\n",
    "                    found = True\n",
    "                    break\n",
    "            if found:\n",
    "                ans = ans_hope\n",
    "            else:\n",
    "                ans <<= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        res, pres, s, total = 0, 1 << 30, set(nums), 0\n",
    "        while pres:\n",
    "            res += pres\n",
    "            total += pres\n",
    "            tag, sp = 0, {x & total for x in s}\n",
    "            for x in s:\n",
    "                if (res ^ x) & total in sp:\n",
    "                    tag = 1\n",
    "                    break\n",
    "            if not tag:\n",
    "                res -= pres\n",
    "            pres >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import log2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: [int]) -> int:\n",
    "        m = max(nums)\n",
    "        n = min(nums)\n",
    "        if m == 0:  # 只有0\n",
    "            return 0\n",
    "        pvt = 2**(int(log2(m)))  # pvt<=max(nums)<pvt*2\n",
    "        while n >= pvt:  # 说明所有数最高位相同，故都减去pvt的异或值相同\n",
    "            nums = [(x - pvt) for x in nums]\n",
    "            m, n = max(nums), min(nums)\n",
    "            if m == 0:\n",
    "                return 0\n",
    "            pvt = 2**(int(log2(m)))\n",
    "        left, right = [], []  # 分别放<pvt和>=pvt的数，且两个列表一定都不为空\n",
    "                              # 需要在left和right中各取一个元素\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < pvt:\n",
    "                left.append((i, nums[i]))  # 把在nums中的序号也储存\n",
    "            else:\n",
    "                right.append((i, nums[i] - pvt))  # right中最高位都一样，去掉后比较\n",
    "\n",
    "        def find(left, right, pvt):\n",
    "            if len(left) == 1 and len(right) == 1 or pvt < 1:\n",
    "                # 都只有一个元素返回；pvt<1说明分到边界，此时left和right中各任选1个都是最优的\n",
    "                return nums[left[0][0]] ^ nums[right[0][0]]\n",
    "            ll, lr, rl, rr = [], [], [], []  # ll lr对left进行切分；rl rr对right进行切分\n",
    "            for i in left:\n",
    "                if i[1] < pvt:\n",
    "                    ll.append(i)\n",
    "                else:\n",
    "                    lr.append((i[0], i[1] - pvt))\n",
    "            for i in right:\n",
    "                if i[1] < pvt:\n",
    "                    rl.append(i)\n",
    "                else:\n",
    "                    rr.append((i[0], i[1] - pvt))\n",
    "            if ll and lr and rl and rr:  # 都不为空，有两种可能，取最优\n",
    "                return max(find(ll, rr, pvt / 2), find(lr, rl, pvt / 2))\n",
    "            elif ll and rr:\n",
    "                return find(ll, rr, pvt / 2)\n",
    "            elif lr and rl:\n",
    "                return find(lr, rl, pvt / 2)\n",
    "            else:\n",
    "                # ll和rr必有一为空，lr和rl必有一为空，又因为left和right一定都非空\n",
    "                # 故选ll和lr中有一个非空，rl和rr中有一个非空，选非空的那两个\n",
    "                temp1 = ll if ll else lr\n",
    "                temp2 = rl if rl else rr\n",
    "                return find(temp1, temp2, pvt / 2)\n",
    "\n",
    "        return find(left, right, pvt / 2)\n",
    "        # left中元素在logpvt+1位都是0，right原本都是1，减去后都是0，故比较log(pvt/2)+1位x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "\n",
    "        def chk(t, s0, s1):\n",
    "            # print(t, s0, s1)\n",
    "            if t < 0:\n",
    "                for i in s0:\n",
    "                    for j in s1:\n",
    "                        return i ^ j\n",
    "                return 0\n",
    "            a0,a1 = set(),set()\n",
    "            b0,b1 = set(),set()\n",
    "            for i in s0:\n",
    "                if (1 << t) & i == 0:\n",
    "                    a0.add(i)\n",
    "                else:\n",
    "                    a1.add(i)\n",
    "            for i in s1:\n",
    "                if (1 << t) & i == 0:\n",
    "                    b0.add(i)\n",
    "                else:\n",
    "                    b1.add(i)\n",
    "            ret = 0\n",
    "            # print(a0,a1,b0,b1)\n",
    "            if len(s1) == 0:\n",
    "                return chk(t-1, a0, a1)\n",
    "            if len(s0) == 0:\n",
    "                return chk(t-1, b0, b1)\n",
    "            if len(a0) and len(b1):\n",
    "                ret = max(ret, chk(t-1, a0, b1))\n",
    "            if len(a1) and len(b0):\n",
    "                ret = max(ret, chk(t-1, b0, a1))\n",
    "            if len(a0) == 0 or len(a1) == 0 or len(b0) == 0 or len(b1) == 0:\n",
    "                if ret == 0:\n",
    "                    ret = max(ret, chk(t-1, s0, s1))\n",
    "            return ret\n",
    "\n",
    "        return chk(32, set(nums), set())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        \n",
    "        root = {}\n",
    "        for num in nums:\n",
    "            tmp = root\n",
    "            for i in range(31, -1, -1):\n",
    "                a = num >> i & 1\n",
    "                if a not in tmp:\n",
    "                    tmp[a] = {}\n",
    "                    tmp = tmp[a]\n",
    "                else:\n",
    "                    tmp = tmp[a]\n",
    "            tmp[2] = num\n",
    "\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            tmp = root\n",
    "            for i in range(31, -1, -1):\n",
    "                a = num >> i & 1\n",
    "                if 1-a in tmp:\n",
    "                    tmp = tmp[1-a]\n",
    "                else:\n",
    "                    tmp = tmp[a]\n",
    "            new = num ^ tmp[2]\n",
    "            if new > res:\n",
    "                res = new\n",
    "        return res\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        def get_min(arr1: set, arr2: set, index: int):\n",
    "            # print(arr1, arr2, index)\n",
    "            if index == -1:\n",
    "                return 0\n",
    "            zero_set1 = set()\n",
    "            zero_set2 = set()\n",
    "            one_set1 = set()\n",
    "            one_set2 = set()\n",
    "            for num in arr1:\n",
    "                if ((num >> index) & 1) == 1:\n",
    "                    one_set1.add(num)\n",
    "                else:\n",
    "                    zero_set1.add(num)\n",
    "            for num in arr2:\n",
    "                if ((num >> index) & 1) == 1:\n",
    "                    one_set2.add(num)\n",
    "                else:\n",
    "                    zero_set2.add(num)\n",
    "            if len(zero_set1) == 0 and len(zero_set2) == 0:\n",
    "                return get_min(one_set1, one_set2, index - 1)\n",
    "            elif len(one_set1) == 0 and len(one_set2) == 0:\n",
    "                return get_min(zero_set1, zero_set2, index - 1)\n",
    "            else:\n",
    "                bit = 1 if len(zero_set1) * len(one_set2) + len(zero_set2) * len(one_set1) > 0 else 0\n",
    "                return (bit << index) | max(get_min(zero_set1, one_set2, index - 1), get_min(zero_set2, one_set1, index - 1))\n",
    "        return get_min(nums, nums, 31)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        BIT_NUM = max(nums).bit_length()\n",
    "        mask = 2 ** (BIT_NUM) - 1\n",
    "        n = len(nums)\n",
    "\n",
    "        class Node:\n",
    "            def __init__(self, v):\n",
    "                self.left = None\n",
    "                self.right = None\n",
    "                self.val = v\n",
    "\n",
    "            def __str__(self):\n",
    "                return '[' + str(self.val) + ', ' + str(self.left) + ', ' + str(self.right) + ']'\n",
    "\n",
    "        root = Node(nums[0])\n",
    "\n",
    "        def add(num: int):\n",
    "            cur = root\n",
    "            for k in reversed(range(BIT_NUM)):\n",
    "                if not cur.left and not cur.right:\n",
    "                    if cur.val & 1 << k:\n",
    "                        cur.right = Node(cur.val)\n",
    "                        if not(num & 1 << k):\n",
    "                            cur.left = Node(num)\n",
    "                            return\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        cur.left = Node(cur.val)\n",
    "                        if num & 1 << k:\n",
    "                            cur.right = Node(num)\n",
    "                            return\n",
    "                        cur = cur.left\n",
    "                else:\n",
    "                    if num & 1 << k:\n",
    "                        if not cur.right:\n",
    "                            cur.right = Node(num)\n",
    "                            return\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        if not cur.left:\n",
    "                            cur.left = Node(num)\n",
    "                            return \n",
    "                        cur = cur.left\n",
    "\n",
    "        def check(num: int) -> int:\n",
    "            cur = root\n",
    "            for k in reversed(range(BIT_NUM)):\n",
    "                if not cur.left and not cur.right:\n",
    "                    return cur.val\n",
    "                if num & 1 << k:\n",
    "                    cur = cur.right if cur.right else cur.left\n",
    "                else:\n",
    "                    cur = cur.left if cur.left else cur.right\n",
    "            return cur.val\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            ans = max(ans, nums[i] ^ check(mask & ~nums[i]))\n",
    "            add(nums[i])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    left: \"Trie\" = None\n",
    "    right: \"Trie\" = None\n",
    "    cnt: int=0\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        ret=0\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        r=Trie()\n",
    "        def insert_trie(num):\n",
    "            cur=r\n",
    "            for i in range(31,-1,-1):\n",
    "                if num&(1<<i):\n",
    "                    if not cur.right:\n",
    "                        cur.right=Trie()\n",
    "                    cur=cur.right\n",
    "                else:\n",
    "                    if not cur.left:\n",
    "                        cur.left=Trie()\n",
    "                    cur=cur.left\n",
    "            cur.cnt+=1\n",
    "        def find(num): #改好了\n",
    "            cur=r\n",
    "            temp=0\n",
    "            for i in range(31,-1,-1):\n",
    "                if num&(1<<i):\n",
    "                    if cur.left:\n",
    "                        temp=temp<<1\n",
    "                        cur=cur.left\n",
    "                    else:\n",
    "                        temp=(temp<<1)+1\n",
    "                        cur=cur.right\n",
    "                else:\n",
    "                    if cur.right:\n",
    "                        temp=(temp<<1)+1\n",
    "                        cur=cur.right\n",
    "                    else:\n",
    "                        temp=temp<<1\n",
    "                        cur=cur.left\n",
    "                #print('sig',temp)\n",
    "            \n",
    "            return temp^num     \n",
    "        ret=0\n",
    "        for i,num in enumerate(nums):\n",
    "            insert_trie(num)\n",
    "            t=find(num)\n",
    "            #print(num,t,num^t)\n",
    "            ret=max(ret,t)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie(object):\n",
    "   def __init__(self):\n",
    "      self.child = {}\n",
    "\n",
    "   def insert(self, word):\n",
    "      current = self.child\n",
    "      for l in word:\n",
    "         if l not in current:\n",
    "            current[l] = {}\n",
    "         current = current[l]\n",
    "      current['#']=1\n",
    "\n",
    "   def startsWith(self, prefix):\n",
    "      current = self.child\n",
    "      for l in prefix:\n",
    "         if l not in current:\n",
    "            return False\n",
    "         current = current[l]\n",
    "      return True\n",
    "\n",
    "# class Trie(object):\n",
    "#     def __init__(self):\n",
    "#         self.root = TrieNode()\n",
    "\n",
    "#     def insert(self, word):\n",
    "#         node = self.root\n",
    "#         for i in range(len(word)):\n",
    "#             if not node.containsKey(word[i]):\n",
    "#                 node.put(word[i], TrieNode())\n",
    "#             node = node.get(word[i])\n",
    "#         node.isEnd = True\n",
    "\n",
    "#     def searchPrefix(self, word):\n",
    "#         node = self.root\n",
    "#         for i in range(len(word)):\n",
    "#             if node.containsKey(word[i]):\n",
    "#                 node = node.get(word[i])\n",
    "#             else:\n",
    "#                 return None\n",
    "#         return node\n",
    "\n",
    "#     def search(self, word):\n",
    "#         node = self.searchPrefix(word)\n",
    "#         return node is not None and node.isEnd\n",
    "\n",
    "#     def startsWith(self, prefix):\n",
    "#         node = self.searchPrefix(prefix)\n",
    "#         return node is not None\n",
    "\n",
    "# class TrieNode:\n",
    "#     def __init__(self):\n",
    "#         self.__R = 2\n",
    "#         self.isEnd = False\n",
    "#         self.links = [None] * self.__R\n",
    "\n",
    "#     def containsKey(self, ch):\n",
    "#         return self.links[ord(ch) - ord('0')] is not None\n",
    "\n",
    "#     def get(self, ch):\n",
    "#         return self.links[ord(ch) - ord('0')]\n",
    "\n",
    "#     def put(self, ch, node):\n",
    "#         self.links[ord(ch) - ord('0')] = node\n",
    "\n",
    "# class Solution:\n",
    "#     def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "#         HIGH_BIT = 30\n",
    "\n",
    "#         x = 0\n",
    "#         for k in range(HIGH_BIT, -1, -1):\n",
    "#             seen = set()\n",
    "#             # 将所有的 pre^k(a_j) 放入哈希表中\n",
    "#             for num in nums: seen.add(num >> k)\n",
    "\n",
    "#             x_next = x * 2 + 1\n",
    "#             found = False\n",
    "            \n",
    "#             for num in nums:\n",
    "#                 if x_next ^ (num >> k) in seen:\n",
    "#                     found = True\n",
    "#                     break\n",
    "\n",
    "#             x = x_next - (0 if found else 1)\n",
    "#         return x\n",
    "\n",
    "# class Trie:\n",
    "#     def __init__(self):\n",
    "#         # 左子树指向表示 0 的子节点\n",
    "#         self.left = None\n",
    "#         # 右子树指向表示 1 的子节点\n",
    "#         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "#         # 字典树的根节点\n",
    "#         root = Trie()\n",
    "#         # 最高位的二进制位编号为 30\n",
    "#         HIGH_BIT = 30\n",
    "\n",
    "#         def add(num: int):\n",
    "#             cur = root\n",
    "#             for k in range(HIGH_BIT, -1, -1):\n",
    "#                 bit = (num >> k) & 1\n",
    "#                 if bit == 0:\n",
    "#                     if not cur.left:\n",
    "#                         cur.left = Trie()\n",
    "#                     cur = cur.left\n",
    "#                 else:\n",
    "#                     if not cur.right:\n",
    "#                         cur.right = Trie()\n",
    "#                     cur = cur.right\n",
    "\n",
    "#         def check(num: int) -> int:\n",
    "#             cur = root\n",
    "#             x = 0\n",
    "#             for k in range(HIGH_BIT, -1, -1):\n",
    "#                 bit = (num >> k) & 1\n",
    "#                 if bit == 0:\n",
    "#                     # a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走\n",
    "#                     if cur.right:\n",
    "#                         cur = cur.right\n",
    "#                         x = x * 2 + 1\n",
    "#                     else:\n",
    "#                         cur = cur.left\n",
    "#                         x = x * 2\n",
    "#                 else:\n",
    "#                     # a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走\n",
    "#                     if cur.left:\n",
    "#                         cur = cur.left\n",
    "#                         x = x * 2 + 1\n",
    "#                     else:\n",
    "#                         cur = cur.right\n",
    "#                         x = x * 2\n",
    "#             return x\n",
    "\n",
    "#         n = len(nums)\n",
    "#         x = 0\n",
    "#         for i in range(1, n):\n",
    "#             # 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中\n",
    "#             add(nums[i - 1])\n",
    "#             # 将 nums[i] 看作 ai，找出最大的 x 更新答案\n",
    "#             x = max(x, check(nums[i]))\n",
    "\n",
    "#         return x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        tr=Trie()\n",
    "        MD=31\n",
    "        def fmxx(b,i,pref,m):\n",
    "            if i==MD:return 0\n",
    "            oz=  '0' if b[i]=='1' else '1'\n",
    "            return  m + fmxx(b,i+1,pref+oz,m>>1) if tr.startsWith(pref+oz) else fmxx(b,i+1,pref+b[i],m>>1)\n",
    "\n",
    "        mx=float('-inf')\n",
    "        for n in nums:\n",
    "            b=bin(n)[2:].zfill(MD)\n",
    "            tr.insert(b)\n",
    "        nums = sorted(nums,reverse=True)\n",
    "\n",
    "        if nums==[0]:return 0\n",
    "        mx2p=int(math.log2(nums[0]))\n",
    "        for n in nums:\n",
    "            b=bin(n)[2:].zfill(MD)\n",
    "            if n and int(math.log2(n))<mx2p:break\n",
    "            mx=max(mx,fmxx(b,0,'',2**(MD-1)))\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie(object):\n",
    "   def __init__(self):\n",
    "      self.child = {}\n",
    "\n",
    "   def insert(self, word):\n",
    "      current = self.child\n",
    "      for l in word:\n",
    "         if l not in current:\n",
    "            current[l] = {}\n",
    "         current = current[l]\n",
    "      current['#']=1\n",
    "\n",
    "   def startsWith(self, prefix):\n",
    "      current = self.child\n",
    "      for l in prefix:\n",
    "         if l not in current:\n",
    "            return False\n",
    "         current = current[l]\n",
    "      return True\n",
    "\n",
    "# class Trie(object):\n",
    "#     def __init__(self):\n",
    "#         self.root = TrieNode()\n",
    "\n",
    "#     def insert(self, word):\n",
    "#         node = self.root\n",
    "#         for i in range(len(word)):\n",
    "#             if not node.containsKey(word[i]):\n",
    "#                 node.put(word[i], TrieNode())\n",
    "#             node = node.get(word[i])\n",
    "#         node.isEnd = True\n",
    "\n",
    "#     def searchPrefix(self, word):\n",
    "#         node = self.root\n",
    "#         for i in range(len(word)):\n",
    "#             if node.containsKey(word[i]):\n",
    "#                 node = node.get(word[i])\n",
    "#             else:\n",
    "#                 return None\n",
    "#         return node\n",
    "\n",
    "#     def search(self, word):\n",
    "#         node = self.searchPrefix(word)\n",
    "#         return node is not None and node.isEnd\n",
    "\n",
    "#     def startsWith(self, prefix):\n",
    "#         node = self.searchPrefix(prefix)\n",
    "#         return node is not None\n",
    "\n",
    "# class TrieNode:\n",
    "#     def __init__(self):\n",
    "#         self.__R = 2\n",
    "#         self.isEnd = False\n",
    "#         self.links = [None] * self.__R\n",
    "\n",
    "#     def containsKey(self, ch):\n",
    "#         return self.links[ord(ch) - ord('0')] is not None\n",
    "\n",
    "#     def get(self, ch):\n",
    "#         return self.links[ord(ch) - ord('0')]\n",
    "\n",
    "#     def put(self, ch, node):\n",
    "#         self.links[ord(ch) - ord('0')] = node\n",
    "\n",
    "# class Solution:\n",
    "#     def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "#         HIGH_BIT = 30\n",
    "\n",
    "#         x = 0\n",
    "#         for k in range(HIGH_BIT, -1, -1):\n",
    "#             seen = set()\n",
    "#             # 将所有的 pre^k(a_j) 放入哈希表中\n",
    "#             for num in nums: seen.add(num >> k)\n",
    "\n",
    "#             x_next = x * 2 + 1\n",
    "#             found = False\n",
    "            \n",
    "#             for num in nums:\n",
    "#                 if x_next ^ (num >> k) in seen:\n",
    "#                     found = True\n",
    "#                     break\n",
    "\n",
    "#             x = x_next - (0 if found else 1)\n",
    "#         return x\n",
    "\n",
    "# class Trie:\n",
    "#     def __init__(self):\n",
    "#         # 左子树指向表示 0 的子节点\n",
    "#         self.left = None\n",
    "#         # 右子树指向表示 1 的子节点\n",
    "#         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "#         # 字典树的根节点\n",
    "#         root = Trie()\n",
    "#         # 最高位的二进制位编号为 30\n",
    "#         HIGH_BIT = 30\n",
    "\n",
    "#         def add(num: int):\n",
    "#             cur = root\n",
    "#             for k in range(HIGH_BIT, -1, -1):\n",
    "#                 bit = (num >> k) & 1\n",
    "#                 if bit == 0:\n",
    "#                     if not cur.left:\n",
    "#                         cur.left = Trie()\n",
    "#                     cur = cur.left\n",
    "#                 else:\n",
    "#                     if not cur.right:\n",
    "#                         cur.right = Trie()\n",
    "#                     cur = cur.right\n",
    "\n",
    "#         def check(num: int) -> int:\n",
    "#             cur = root\n",
    "#             x = 0\n",
    "#             for k in range(HIGH_BIT, -1, -1):\n",
    "#                 bit = (num >> k) & 1\n",
    "#                 if bit == 0:\n",
    "#                     # a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走\n",
    "#                     if cur.right:\n",
    "#                         cur = cur.right\n",
    "#                         x = x * 2 + 1\n",
    "#                     else:\n",
    "#                         cur = cur.left\n",
    "#                         x = x * 2\n",
    "#                 else:\n",
    "#                     # a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走\n",
    "#                     if cur.left:\n",
    "#                         cur = cur.left\n",
    "#                         x = x * 2 + 1\n",
    "#                     else:\n",
    "#                         cur = cur.right\n",
    "#                         x = x * 2\n",
    "#             return x\n",
    "\n",
    "#         n = len(nums)\n",
    "#         x = 0\n",
    "#         for i in range(1, n):\n",
    "#             # 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中\n",
    "#             add(nums[i - 1])\n",
    "#             # 将 nums[i] 看作 ai，找出最大的 x 更新答案\n",
    "#             x = max(x, check(nums[i]))\n",
    "\n",
    "#         return x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        #tr=Trie()\n",
    "        pfset=set()\n",
    "        MD=31\n",
    "        def fmxx(b,i,pref,m):\n",
    "            if i==MD:return 0\n",
    "            oz=  '0' if b[i]=='1' else '1'\n",
    "            return  m + fmxx(b,i+1,pref+oz,m>>1) if pref+oz in pfset else fmxx(b,i+1,pref+b[i],m>>1)\n",
    "            #return  m + fmxx(b,i+1,pref+oz,m>>1) if tr.startsWith(pref+oz) else fmxx(b,i+1,pref+b[i],m>>1)\n",
    "\n",
    "        mx=float('-inf')\n",
    "        for n in nums:\n",
    "            b=bin(n)[2:].zfill(MD)\n",
    "            for i in range(1,MD+1):pfset.add(b[:i])\n",
    "            #tr.insert(b)\n",
    "        nums = sorted(nums,reverse=True)\n",
    "\n",
    "        if nums==[0]:return 0\n",
    "        mx2p=int(math.log2(nums[0]))\n",
    "        for n in nums:\n",
    "            b=bin(n)[2:].zfill(MD)\n",
    "            if n and int(math.log2(n))<mx2p:break\n",
    "            mx=max(mx,fmxx(b,0,'',2**(MD-1)))\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryTrie:\n",
    "    \"\"\"\n",
    "    Reference:\n",
    "     - https://atcoder.jp/contests/arc028/submissions/19916627\n",
    "     - https://judge.yosupo.jp/submission/35057\n",
    "    \"\"\"\n",
    "\n",
    "    __slots__ = (\n",
    "        \"max_log\",\n",
    "        \"x_end\",\n",
    "        \"v_list\",\n",
    "        \"multiset\",\n",
    "        \"add_query_count\",\n",
    "        \"add_query_limit\",\n",
    "        \"edges\",\n",
    "        \"size\",\n",
    "        \"is_end\",\n",
    "        \"max_v\",\n",
    "        \"lazy\",\n",
    "    )\n",
    "\n",
    "    def __init__(\n",
    "        self,\n",
    "        max_log=31,\n",
    "        allow_multiple_elements=True,\n",
    "        add_query_limit=10**6,\n",
    "    ):\n",
    "        self.max_log = max_log\n",
    "        self.x_end = 1 << max_log\n",
    "        self.v_list = [0] * (max_log + 1)\n",
    "        self.multiset = allow_multiple_elements\n",
    "        self.add_query_count = 0\n",
    "        self.add_query_limit = add_query_limit\n",
    "        n = max_log * add_query_limit + 1\n",
    "        self.edges = [-1] * (2 * n)\n",
    "        self.size = [0] * n\n",
    "        self.is_end = [0] * n\n",
    "        self.max_v = 0\n",
    "        self.lazy = 0\n",
    "\n",
    "    def add(self, x: int):\n",
    "        # assert 0 <= x < self.x_end\n",
    "        # assert 0 <= self.add_query_count < self.add_query_limit\n",
    "        x ^= self.lazy\n",
    "        v = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            d = (x >> i) % 2\n",
    "            if self.edges[2 * v + d] == -1:\n",
    "                self.max_v += 1\n",
    "                self.edges[2 * v + d] = self.max_v\n",
    "            v = self.edges[2 * v + d]\n",
    "            self.v_list[i] = v\n",
    "        if self.multiset or self.is_end[v] == 0:\n",
    "            self.is_end[v] += 1\n",
    "            for v in self.v_list:\n",
    "                self.size[v] += 1\n",
    "        self.add_query_count += 1\n",
    "\n",
    "    def discard(self, x: int):\n",
    "        if not 0 <= x < self.x_end:\n",
    "            return\n",
    "        x ^= self.lazy\n",
    "        v = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            d = (x >> i) % 2\n",
    "            if self.edges[2 * v + d] == -1:\n",
    "                return\n",
    "            v = self.edges[2 * v + d]\n",
    "            self.v_list[i] = v\n",
    "        if self.is_end[v] > 0:\n",
    "            self.is_end[v] -= 1\n",
    "            for v in self.v_list:\n",
    "                self.size[v] -= 1\n",
    "\n",
    "    def erase(self, x: int, count: int = -1):\n",
    "        \"\"\"删除count个x x=-1表示删除所有x\"\"\"\n",
    "        # assert -1 <= count\n",
    "        if not 0 <= x < self.x_end:\n",
    "            return\n",
    "        x ^= self.lazy\n",
    "        v = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            d = (x >> i) % 2\n",
    "            if self.edges[2 * v + d] == -1:\n",
    "                return\n",
    "            v = self.edges[2 * v + d]\n",
    "            self.v_list[i] = v\n",
    "        if count == -1 or self.is_end[v] < count:\n",
    "            count = self.is_end[v]\n",
    "        if self.is_end[v] > 0:\n",
    "            self.is_end[v] -= count\n",
    "            for v in self.v_list:\n",
    "                self.size[v] -= count\n",
    "\n",
    "    def count(self, x: int) -> int:\n",
    "        if not 0 <= x < self.x_end:\n",
    "            return 0\n",
    "        x ^= self.lazy\n",
    "        v = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            d = (x >> i) % 2\n",
    "            if self.edges[2 * v + d] == -1:\n",
    "                return 0\n",
    "            v = self.edges[2 * v + d]\n",
    "        return self.is_end[v]\n",
    "\n",
    "    def bisect_left(self, x: int) -> int:\n",
    "        if x < 0:\n",
    "            return 0\n",
    "        if self.x_end <= x:\n",
    "            return len(self)\n",
    "        v = 0\n",
    "        ret = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            d = (x >> i) % 2\n",
    "            l = (self.lazy >> i) % 2\n",
    "            lc = self.edges[2 * v]\n",
    "            rc = self.edges[2 * v + 1]\n",
    "            if l == 1:\n",
    "                lc, rc = rc, lc\n",
    "            if d:\n",
    "                if lc != -1:\n",
    "                    ret += self.size[lc]\n",
    "                if rc == -1:\n",
    "                    return ret\n",
    "                v = rc\n",
    "            else:\n",
    "                if lc == -1:\n",
    "                    return ret\n",
    "                v = lc\n",
    "        return ret\n",
    "\n",
    "    def bisect_right(self, x: int) -> int:\n",
    "        return self.bisect_left(x + 1)\n",
    "\n",
    "    def index(self, x: int) -> int:\n",
    "        if x not in self:\n",
    "            raise ValueError(f\"{x} is not in BinaryTrie\")\n",
    "        return self.bisect_left(x)\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if x not in self:\n",
    "            return -1\n",
    "        return self.bisect_left(x)\n",
    "\n",
    "    def kth_elem(self, k: int) -> int:\n",
    "        if k < 0:\n",
    "            k += self.size[0]\n",
    "        # assert 0 <= k < self.size[0]\n",
    "        v = 0\n",
    "        ret = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            l = (self.lazy >> i) % 2\n",
    "            lc = self.edges[2 * v]\n",
    "            rc = self.edges[2 * v + 1]\n",
    "            if l == 1:\n",
    "                lc, rc = rc, lc\n",
    "            if lc == -1:\n",
    "                v = rc\n",
    "                ret |= 1 << i\n",
    "                continue\n",
    "            if self.size[lc] <= k:\n",
    "                k -= self.size[lc]\n",
    "                v = rc\n",
    "                ret |= 1 << i\n",
    "            else:\n",
    "                v = lc\n",
    "        return ret\n",
    "\n",
    "    def minimum(self) -> int:\n",
    "        if self.size[0] == 0:\n",
    "            return 1 << self.max_log\n",
    "        return self.kth_elem(0)\n",
    "\n",
    "    def maximum(self) -> int:\n",
    "        if self.size[0] == 0:\n",
    "            return - (1 << self.max_log)\n",
    "        return self.kth_elem(-1)\n",
    "\n",
    "    def xor_all(self, x: int):\n",
    "        # assert 0 <= x < self.x_end\n",
    "        self.lazy ^= x\n",
    "\n",
    "    def __iter__(self):\n",
    "        q = [(0, 0)]\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            l = (self.lazy >> i) % 2\n",
    "            nq = []\n",
    "            for v, x in q:\n",
    "                lc = self.edges[2 * v]\n",
    "                rc = self.edges[2 * v + 1]\n",
    "                if l == 1:\n",
    "                    lc, rc = rc, lc\n",
    "                if lc != -1:\n",
    "                    nq.append((lc, 2 * x))\n",
    "                if rc != -1:\n",
    "                    nq.append((rc, 2 * x + 1))\n",
    "            q = nq\n",
    "        for v, x in q:\n",
    "            for _ in range(self.is_end[v]):\n",
    "                yield x\n",
    "\n",
    "    def __str__(self):\n",
    "        prefix = \"BinaryTrie(\"\n",
    "        content = list(map(str, self))\n",
    "        suffix = \")\"\n",
    "        if content:\n",
    "            content[0] = prefix + content[0]\n",
    "            content[-1] = content[-1] + suffix\n",
    "        else:\n",
    "            content = [prefix + suffix]\n",
    "        return \", \".join(content)\n",
    "\n",
    "    def __getitem__(self, k):\n",
    "        return self.kth_elem(k)\n",
    "\n",
    "    def __contains__(self, x: int) -> bool:\n",
    "        return not not self.count(x)\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size[0]\n",
    "\n",
    "    def __bool__(self):\n",
    "        return not not len(self)\n",
    "\n",
    "    def __ixor__(self, x: int):\n",
    "        self.xor_all(x)\n",
    "        return self\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, A: List[int]) -> int:\n",
    "\n",
    "        bt = BinaryTrie(max(A).bit_length(), False, len(A))\n",
    "        res = -1\n",
    "        for x in A:\n",
    "            bt.add(x)\n",
    "            bt ^= x\n",
    "            res = max(res, bt.maximum())\n",
    "            # print(x, bt.maximum(), res)\n",
    "            # print(x, [y for y in bt], bt.minimum(), bt.maximum())\n",
    "            bt ^= x\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\r\n",
    "    def __init__(self, bt=-1) -> None:\r\n",
    "        self.ch = {}\r\n",
    "        self.bt = bt\r\n",
    "\r\n",
    "    def insert(self, n):\r\n",
    "        cur_node = self\r\n",
    "        for bl in range(31, 0, -1):\r\n",
    "            cur_bit = (n >> bl) & 1\r\n",
    "            if cur_bit not in cur_node.ch:\r\n",
    "                cur_node.ch[cur_bit] = Trie()\r\n",
    "            cur_node = cur_node.ch[cur_bit]\r\n",
    "        cur_node.bt = n\r\n",
    "\r\n",
    "    def search(self, n):\r\n",
    "        cur_node = self\r\n",
    "        for bl in range(31, 0, -1):\r\n",
    "            cur_bit = (n >> bl) & 1\r\n",
    "            cur_node = cur_node.ch[(1 - cur_bit) if (1 - cur_bit) in cur_node.ch else cur_bit]\r\n",
    "        return cur_node.bt\r\n",
    "            \r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\r\n",
    "        t = Trie()\r\n",
    "        for n in nums:\r\n",
    "            t.insert(n)\r\n",
    "\r\n",
    "        res = 0\r\n",
    "        for n in nums:\r\n",
    "            res = max(res, n ^ t.search(n))\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        class Node:\n",
    "            def __init__(self):\n",
    "                self.next = [None] * 2\n",
    "                \n",
    "        rt = Node()\n",
    "        \n",
    "        def add(aV, aP):\n",
    "            n, dp = rt, aP\n",
    "            ret = 0\n",
    "            for c in aV:\n",
    "                i = 0 if '0' == c else 1                \n",
    "                if None == n.next[i]:\n",
    "                    n.next[i] = Node()\n",
    "                    ret = max(dp, ret)\n",
    "                n = n.next[i]\n",
    "                dp -= 1\n",
    "            return ret\n",
    "                \n",
    "        def xor(aV, aP):\n",
    "            n, dp, ret = rt, aP, 0\n",
    "            # print(f\"av {aV} n {n}\")\n",
    "            for c in aV:\n",
    "                i = 1 if '0' == c else 0\n",
    "                if n.next[i] != None:\n",
    "                    # print(f\"find next {i}\")\n",
    "                    n = n.next[i]\n",
    "                    ret = ret + 2 ** dp\n",
    "                else:\n",
    "                    # print(f\"can,t find next {i} {n.next}\")\n",
    "                    n = n.next[1 - i]\n",
    "                # print(f\"ck dp{dp} n {n}\")\n",
    "                dp -= 1\n",
    "            return ret\n",
    "            \n",
    "        lv = [2 ** i for i in range(32)]\n",
    "        p = 0\n",
    "        for n in nums:\n",
    "            while n > lv[p]:\n",
    "                p += 1\n",
    "        # print(f\"p {p} {lv[p]}\")\n",
    "        maxV = lv[p] - 1\n",
    "        # def getMaxV:\n",
    "            \n",
    "        ret, rPos = 0, -1\n",
    "        fmt = \"{\" + f\":0{p + 1}b\" + \"}\"\n",
    "        # print(f\"use fmt {fmt}\")\n",
    "        for n in nums:\n",
    "            v = fmt.format(n)\n",
    "            dPos = add(v, p)\n",
    "            # print(f\" {n} {v} dPos {dPos} {xor(v, p)}\")\n",
    "            if dPos > rPos:\n",
    "                ret = max(ret, xor(v, p))\n",
    "                # print(f\" ret {ret}\")\n",
    "                if ret > 0 and 0 == ret & (ret + 1):\n",
    "                    rPos = dPos\n",
    "                    if maxV == ret:\n",
    "                        # print(f\"reach max\")\n",
    "                        return ret\n",
    "        # print(bin(ret), \"@@@\", cnt)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.children: Dict[str, TrieNode] = {}\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        cur = self.root\n",
    "        for letter in word:\n",
    "            if letter not in cur.children:\n",
    "                cur.children[letter] = TrieNode()\n",
    "            cur = cur.children[letter]\n",
    "\n",
    "    \"\"\"def startsWith(self, prefix: str) -> bool:\n",
    "        cur = self.root\n",
    "        for letter in prefix:\n",
    "            if letter in cur.children:\n",
    "                cur = cur.children[letter]\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "    \"\"\"\n",
    "    \n",
    "    def xor(self, num: str) -> int:\n",
    "        optimal = [\n",
    "            '0' if digit == '1'\n",
    "            else '1'\n",
    "            for digit in num\n",
    "        ]\n",
    "        res = 0\n",
    "        cur = self.root\n",
    "        for digit in optimal:\n",
    "            res <<= 1\n",
    "            if digit in cur.children:\n",
    "                if digit == '1':\n",
    "                    res += 1\n",
    "                cur = cur.children[digit]\n",
    "            else:\n",
    "                if digit == '0':\n",
    "                    res += 1\n",
    "                cur = cur.children['0' if digit == '1' else '1']\n",
    "        return res ^ int(num, 2)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        myTrie = Trie()\n",
    "        nums = list(set(nums))\n",
    "        max_num = -float('inf')\n",
    "        max_index = -1\n",
    "        for i, num in enumerate(nums):\n",
    "            if num > max_num:\n",
    "                max_num = num\n",
    "                max_index = i\n",
    "        max_len = len(bin(nums[max_index])) - 2\n",
    "        nums = list(map(lambda x: bin(x)[2:].zfill(max_len), nums))\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            myTrie.insert(num)\n",
    "        for num in nums:\n",
    "            res = max(res, myTrie.xor(num))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Node:\n",
    "    __slots__ = ('_left', '_right')\n",
    "    def __init__(self):\n",
    "        self._left = None\n",
    "        self._right = None\n",
    "    \n",
    "    @property\n",
    "    def left(self):\n",
    "        return self._left\n",
    "    \n",
    "    @property\n",
    "    def right(self):\n",
    "        return self._right\n",
    "        \n",
    "    @left.setter\n",
    "    def left(self, node):\n",
    "        self._left = node\n",
    "        \n",
    "    @right.setter\n",
    "    def right(self, node):\n",
    "        self._right = node\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        root = Node()\n",
    "        \n",
    "        def append(num):\n",
    "            cur = root\n",
    "            # 从高位开始向地位逐位截取\n",
    "            for i in range(31, -1, -1):\n",
    "                dig = (num >> i) & 1\n",
    "                # 0 向左 1 向右\n",
    "                if dig == 0:\n",
    "                    if cur.left is None:\n",
    "                        cur.left = Node()\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    if cur.right is None:\n",
    "                        cur.right = Node()\n",
    "                    cur = cur.right\n",
    "        \n",
    "        def calc(input):\n",
    "            cur = root\n",
    "            res = 0\n",
    "            # 同样从高位开始向低位逐位截取\n",
    "            for i in range(31, -1, -1):\n",
    "                dig = (input >> i) & 1\n",
    "                if dig == 0:\n",
    "                    # 当输入位为 0 时, 优先选择 1, 确保异或值最大\n",
    "                    if cur.right:\n",
    "                        # 1 存在, 则异或值为 1, 并向左移动\n",
    "                        res = res * 2 + 1\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        # 1 不存在, 则异或值为 0, 并向左移动\n",
    "                        res = res * 2\n",
    "                        cur = cur.left\n",
    "                else:\n",
    "                    if cur.left:\n",
    "                        res = res * 2 + 1\n",
    "                        cur = cur.left\n",
    "                    else:\n",
    "                        res = res * 2\n",
    "                        cur = cur.right\n",
    "            return res\n",
    "        \n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            append(num)\n",
    "            ans = max(ans, calc(num))\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "HIGTH_BIT = 30\n",
    "\n",
    "class TrieNode:\n",
    "    __slots__ = ['left', 'right']\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    __slots__ = ['root']\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, num: int) -> None:\n",
    "        cur = self.root\n",
    "        for k in range(HIGTH_BIT, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            if bit == 0:\n",
    "                if not cur.left:\n",
    "                    cur.left = TrieNode()\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                if not cur.right:\n",
    "                    cur.right = TrieNode()\n",
    "                cur = cur.right\n",
    "\n",
    "    def search(self, num: int) -> int:\n",
    "        cur = self.root\n",
    "        x = 0\n",
    "        for k in range(HIGTH_BIT, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            if bit == 0:\n",
    "                if cur.right:\n",
    "                    cur = cur.right\n",
    "                    x = x * 2 + 1\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "                    x = x * 2\n",
    "            else:\n",
    "                if cur.left:\n",
    "                    cur = cur.left\n",
    "                    x = x * 2 + 1\n",
    "                else:\n",
    "                    cur = cur.right\n",
    "                    x = x * 2\n",
    "\n",
    "        return x\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        res  = 0\n",
    "        trie = Trie()\n",
    "\n",
    "        for i in range(1, n):\n",
    "            trie.insert(nums[i - 1])\n",
    "            res = max(res, trie.search(nums[i]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        dig, k = [], 1\n",
    "        for i in range(31):\n",
    "            dig = [k] + dig\n",
    "            k <<= 1\n",
    "        \n",
    "        pos = [0,0,0]\n",
    "        root, idx = 1, 3\n",
    "        for v in nums:\n",
    "            cur = root\n",
    "            for i in dig:\n",
    "                t = 1 if (i & v > 0) else 0\n",
    "                if pos[cur+t] == 0:\n",
    "                    pos.extend([0,0])\n",
    "                    pos[cur+t] = idx\n",
    "                    idx += 2\n",
    "                cur = pos[cur+t]\n",
    "            pos[cur] = 1\n",
    "        mmax = 0\n",
    "        for v in nums:\n",
    "            cur = root\n",
    "            res = 0\n",
    "            for i in dig:\n",
    "                t = 0 if (i & v > 0) else 1\n",
    "                if pos[cur+t] == 0:\n",
    "                    t = 1 - t\n",
    "                else:\n",
    "                    res |= i\n",
    "                cur = pos[cur+t]\n",
    "                if res + i < mmax:\n",
    "                    break\n",
    "            mmax = max(mmax, res)\n",
    "\n",
    "        return mmax                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        root = TrieNode()\n",
    "        ans = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            root.add(nums[i-1])\n",
    "            ans = max(ans,root.search(nums[i]))\n",
    "        return ans\n",
    "\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.son = defaultdict(TrieNode)\n",
    "        self.num = []\n",
    "    def add(self,num):\n",
    "        p = self\n",
    "        for i in range(31,-1,-1):\n",
    "            k = num>>i & 1\n",
    "            p = p.son[k]\n",
    "        p.num=num\n",
    "    def search(self,num)->int:\n",
    "        p = self\n",
    "        for i in range(31,-1,-1):\n",
    "            k = num>>i & 1\n",
    "            if k^1 in p.son:\n",
    "                p = p.son[k^1]\n",
    "            elif k in p.son:\n",
    "                p = p.son[k]\n",
    "            else:\n",
    "                break\n",
    "        return p.num^num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryTrie:\n",
    "    def __init__(self, max_bit: int = 30):\n",
    "        self.inf = 1 << 63\n",
    "        self.to = [[-1], [-1]]\n",
    "        self.cnt = [0]\n",
    "        self.max_bit = max_bit\n",
    "\n",
    "    def add(self, num: int) -> None:\n",
    "        cur = 0\n",
    "        self.cnt[cur] += 1\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            if self.to[bit][cur] == -1:\n",
    "                self.to[bit][cur] = len(self.cnt)\n",
    "                self.to[0].append(-1)\n",
    "                self.to[1].append(-1)\n",
    "                self.cnt.append(0)\n",
    "            cur = self.to[bit][cur]\n",
    "            self.cnt[cur] += 1\n",
    "        return\n",
    "\n",
    "    def remove(self, num: int) -> bool:\n",
    "        if self.cnt[0] == 0:\n",
    "            return False\n",
    "        cur = 0\n",
    "        rm = [0]\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0:\n",
    "                return False\n",
    "            rm.append(cur)\n",
    "        for cur in rm:\n",
    "            self.cnt[cur] -= 1\n",
    "        return True\n",
    "\n",
    "    def count(self, num: int):\n",
    "        cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0:\n",
    "                return 0\n",
    "        return self.cnt[cur]\n",
    "\n",
    "    # Get max result for constant x ^ element in array\n",
    "    def max_xor(self, x: int) -> int:\n",
    "        if self.cnt[0] == 0:\n",
    "            return -self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit ^ 1][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                cur = self.to[bit][cur]\n",
    "            else:\n",
    "                res |= 1 << k\n",
    "                cur = nxt\n",
    "\n",
    "        return res\n",
    "\n",
    "    # Get min result for constant x ^ element in array\n",
    "    def min_xor(self, x: int) -> int:\n",
    "        if self.cnt[0] == 0:\n",
    "            return self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                res |= 1 << k\n",
    "                cur = self.to[bit ^ 1][cur]\n",
    "            else:\n",
    "                cur = nxt\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        bt = BinaryTrie(32)\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            bt.add(num)\n",
    "            cur = bt.max_xor(num)\n",
    "            if cur > ans:\n",
    "                ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "    from time import time\n",
    "    # create a binary tree, then search the top&long symmetry path\n",
    "    i = max(nums)\n",
    "    if not i: # i=0 leads k be 0, not desired 1 as i=1.\n",
    "      #i = 0x40041000\n",
    "      #nums = range(0x40001000, i)\n",
    "      return 0\n",
    "    k = 0 # not -1, to create one more top layer for root.\n",
    "    while i:\n",
    "      k += 1\n",
    "      i >>= 1\n",
    "    t, e, ik, t0 = [0,0], 2, 1<<k, time()\n",
    "    for v in nums:\n",
    "      p, i = 0, ik\n",
    "      for _ in range(k):\n",
    "        if v&i:\n",
    "          p += 1\n",
    "        if not t[p]:\n",
    "          t[p] = e\n",
    "          p = e\n",
    "          t += [0, 0]\n",
    "          e += 2\n",
    "        else:\n",
    "          p = t[p]\n",
    "        i >>= 1\n",
    "      t[p + (v&1)] = 1 # leaf layer is special: 0/1 is not index.\n",
    "    t1 = time()\n",
    "    #print(list(enumerate(t[:e])))\n",
    "    #print(t[:e])\n",
    "\n",
    "    def sym(k, l, r):\n",
    "      if not k:\n",
    "        return 0 # leaf layer has no child\n",
    "      #print(k, l, '--', r)\n",
    "      k -= 1\n",
    "      if not r:\n",
    "        l, r = t[l:l+2]\n",
    "        if l and r:\n",
    "          return (1<<k) | sym(k, l, r)\n",
    "        return sym(k, l, r)\n",
    "      if not l:\n",
    "        l, r = t[r:r+2]\n",
    "        if l and r:\n",
    "          return (1<<k) | sym(k, l, r)\n",
    "        return sym(k, l, r)\n",
    "      match( (8 if t[l] else 0) | (4 if t[l+1] else 0) | \n",
    "             (2 if t[r] else 0) | (1 if t[r+1] else 0) ):\n",
    "        case 0b1111:\n",
    "          return (1<<k) | max(sym(k, t[l], t[r+1]), sym(k, t[l+1], t[r]))\n",
    "        case 0b1001 | 0b1101 | 0b1011:\n",
    "          return (1<<k) | sym(k, t[l], t[r+1])\n",
    "        case 0b0110 | 0b1110 | 0b0111:\n",
    "          return (1<<k) | sym(k, t[l+1], t[r])\n",
    "        case 0b1010:\n",
    "          return sym(k, t[l], t[r])\n",
    "        case 0b0101:\n",
    "          return sym(k, t[l+1], t[r+1])\n",
    "        case _:  # bb00/00bb, 7 in total. should not be here.\n",
    "          print('bb00/00bb')\n",
    "\n",
    "    res = sym(k, 2, 0) # t[0:2]=[2,0], root is special\n",
    "    t2 = time()\n",
    "    if t2 - t0 > 0.3:\n",
    "      print('%.3f %.3f'%(t1 - t0, t2 - t1))\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryTrie:\n",
    "    def __init__(self, max_bit=30):\n",
    "        self.inf = 1 << 63\n",
    "        self.to = [[-1], [-1]]\n",
    "        self.cnt = [0]\n",
    "        self.max_bit = max_bit\n",
    "    \n",
    "    def add(self, num):\n",
    "        cur = 0\n",
    "        self.cnt[cur] += 1\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            if self.to[bit][cur] == -1:\n",
    "                self.to[bit][cur] = len(self.cnt)\n",
    "                self.to[0].append(-1)\n",
    "                self.to[1].append(-1)\n",
    "                self.cnt.append(0)\n",
    "            cur = self.to[bit][cur]\n",
    "            self.cnt[cur] += 1\n",
    "    \n",
    "    def remove(num):\n",
    "        if self.cnt[0] == 0: return False\n",
    "        cur = 0\n",
    "        rm = [0]\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0: return False\n",
    "            rm.append(cur)\n",
    "        for cur in rm:\n",
    "            self.cnt[cur] -= 1\n",
    "        return True\n",
    "    \n",
    "    def count(self, num):\n",
    "        cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0: return 0\n",
    "        return self.cnt[cur]\n",
    "    \n",
    "    def max_xor(self, x):\n",
    "        if self.cnt[0] == 0: return -self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit ^ 1][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                cur = self.to[bit][cur]\n",
    "            else:\n",
    "                cur = nxt\n",
    "                res |= 1 << k\n",
    "        return res\n",
    "    \n",
    "    def min_xor(self, x):\n",
    "        if self.cnt[0] == 0: return self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                res |= 1 << k\n",
    "                cur = self.to[bit ^ 1][cur]\n",
    "            else:\n",
    "                cur = nxt\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        trie = BinaryTrie()\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if i:\n",
    "                res = max(res, trie.max_xor(x))\n",
    "            trie.add(x)\n",
    "        return res\n",
    "\n",
    "        # root = Trie()\n",
    "        # HIGH_BIT = 30\n",
    "        # def add(num):\n",
    "        #     cur = root\n",
    "        #     for k in range(HIGH_BIT, -1, -1):\n",
    "        #         bit = (num >> k) & 1\n",
    "        #         if bit == 0:\n",
    "        #             if not cur.left:\n",
    "        #                 cur.left = Trie()\n",
    "        #             cur = cur.left\n",
    "        #         else:\n",
    "        #             if not cur.right:\n",
    "        #                 cur.right = Trie()\n",
    "        #             cur = cur.right\n",
    "        \n",
    "        # def check(num):\n",
    "        #     cur = root\n",
    "        #     x = 0\n",
    "        #     for k in range(HIGH_BIT, -1, -1):\n",
    "        #         bit = (num >> k) & 1\n",
    "        #         if bit == 0:\n",
    "        #             if cur.right:\n",
    "        #                 cur = cur.right\n",
    "        #                 x = x * 2 + 1\n",
    "        #             else:\n",
    "        #                 cur = cur.left\n",
    "        #                 x = x * 2\n",
    "        #         else:\n",
    "        #             if cur.left:\n",
    "        #                 cur = cur.left\n",
    "        #                 x = x * 2 + 1\n",
    "        #             else:\n",
    "        #                 cur = cur.right\n",
    "        #                 x = x * 2\n",
    "        #     return x \n",
    "        \n",
    "        # n = len(nums)\n",
    "        # res = 0\n",
    "        # for i in range(1, n):\n",
    "        #     add(nums[i - 1])\n",
    "        #     res = max(res, check(nums[i]))\n",
    "        # return res\n",
    "\n",
    "        # res = mask = 0\n",
    "        # for i in range(30, -1, -1):\n",
    "        #     mask |= 1 << i\n",
    "        #     s = set(mask & x for x in nums)\n",
    "        #     cur = res | 1 << i\n",
    "        #     for x in s:\n",
    "        #         if cur ^ x in s:\n",
    "        #             res = cur\n",
    "        #             break\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryTrie:\n",
    "    def __init__(self, max_bit: int = 30):\n",
    "        self.inf = 1 << 63\n",
    "        self.to = [[-1], [-1]]\n",
    "        self.cnt = [0]\n",
    "        self.max_bit = max_bit\n",
    "\n",
    "    def add(self, num: int) -> None:\n",
    "        cur = 0\n",
    "        self.cnt[cur] += 1\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            if self.to[bit][cur] == -1:\n",
    "                self.to[bit][cur] = len(self.cnt)\n",
    "                self.to[0].append(-1)\n",
    "                self.to[1].append(-1)\n",
    "                self.cnt.append(0)\n",
    "            cur = self.to[bit][cur]\n",
    "            self.cnt[cur] += 1\n",
    "\n",
    "    def remove(self, num: int) -> bool:\n",
    "        if self.cnt[0] == 0: return False\n",
    "        cur = 0\n",
    "        rm = [0]\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0: return False\n",
    "            rm.append(cur)\n",
    "        for cur in rm: self.cnt[cur] -= 1\n",
    "        return True\n",
    "\n",
    "    def count(self, num: int):\n",
    "        cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0: return 0\n",
    "        return self.cnt[cur]\n",
    "\n",
    "    # Get max result for constant x ^ element in array\n",
    "    def max_xor(self, x: int) -> int:\n",
    "        if self.cnt[0] == 0: return -self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit ^ 1][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                cur = self.to[bit][cur]\n",
    "            else:\n",
    "                cur = nxt\n",
    "                res |= 1 << k\n",
    "        return res\n",
    "\n",
    "    # Get min result for constant x ^ element in array\n",
    "    def min_xor(self, x: int) -> int:\n",
    "        if self.cnt[0] == 0: return self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                res |= 1 << k\n",
    "                cur = self.to[bit ^ 1][cur]\n",
    "            else:\n",
    "                cur = nxt\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        trie = BinaryTrie()\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if i:\n",
    "                res = max(res, trie.max_xor(x))\n",
    "            trie.add(x)\n",
    "        return res\n",
    "\n",
    "        # root = Trie()\n",
    "        # HIGH_BIT = 30\n",
    "        # def add(num):\n",
    "        #     cur = root\n",
    "        #     for k in range(HIGH_BIT, -1, -1):\n",
    "        #         bit = (num >> k) & 1\n",
    "        #         if bit == 0:\n",
    "        #             if not cur.left:\n",
    "        #                 cur.left = Trie()\n",
    "        #             cur = cur.left\n",
    "        #         else:\n",
    "        #             if not cur.right:\n",
    "        #                 cur.right = Trie()\n",
    "        #             cur = cur.right\n",
    "        \n",
    "        # def check(num):\n",
    "        #     cur = root\n",
    "        #     x = 0\n",
    "        #     for k in range(HIGH_BIT, -1, -1):\n",
    "        #         bit = (num >> k) & 1\n",
    "        #         if bit == 0:\n",
    "        #             if cur.right:\n",
    "        #                 cur = cur.right\n",
    "        #                 x = x * 2 + 1\n",
    "        #             else:\n",
    "        #                 cur = cur.left\n",
    "        #                 x = x * 2\n",
    "        #         else:\n",
    "        #             if cur.left:\n",
    "        #                 cur = cur.left\n",
    "        #                 x = x * 2 + 1\n",
    "        #             else:\n",
    "        #                 cur = cur.right\n",
    "        #                 x = x * 2\n",
    "        #     return x \n",
    "        \n",
    "        # n = len(nums)\n",
    "        # res = 0\n",
    "        # for i in range(1, n):\n",
    "        #     add(nums[i - 1])\n",
    "        #     res = max(res, check(nums[i]))\n",
    "        # return res\n",
    "\n",
    "        # res = mask = 0\n",
    "        # for i in range(30, -1, -1):\n",
    "        #     mask |= 1 << i\n",
    "        #     s = set(mask & x for x in nums)\n",
    "        #     cur = res | 1 << i\n",
    "        #     for x in s:\n",
    "        #         if cur ^ x in s:\n",
    "        #             res = cur\n",
    "        #             break\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class XorTrieSimpleNode:\n",
    "    __slots__ = \"count\", \"zero\", \"one\"\n",
    "\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "        self.zero = None\n",
    "        self.one = None\n",
    "\n",
    "\n",
    "class XorTrieSimple:\n",
    "    __slots__ = \"root\", \"bit\"\n",
    "\n",
    "    def __init__(self, upper: int):\n",
    "        self.root = XorTrieSimpleNode()\n",
    "        self.bit = upper.bit_length()\n",
    "\n",
    "    def insert(self, num: int) -> \"XorTrieSimpleNode\":\n",
    "        root = self.root\n",
    "        for i in range(self.bit, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            if bit:\n",
    "                if root.one is None:\n",
    "                    root.one = XorTrieSimpleNode()\n",
    "                root = root.one\n",
    "            else:\n",
    "                if root.zero is None:\n",
    "                    root.zero = XorTrieSimpleNode()\n",
    "                root = root.zero\n",
    "            root.count += 1\n",
    "        return root\n",
    "\n",
    "    def remove(self, num: int) -> None:\n",
    "        \"\"\"需要保证num在trie中.\"\"\"\n",
    "        root = self.root\n",
    "        for i in range(self.bit, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            root = bit.one if bit else root.zero  # type: ignore\n",
    "            root.count -= 1  # type: ignore\n",
    "\n",
    "    def query(self, num: int) -> int:\n",
    "        \"\"\"查询num与trie中的最大异或值.\"\"\"\n",
    "        root = self.root\n",
    "        res = 0\n",
    "        for i in range(self.bit, -1, -1):\n",
    "            if root is None:  # type: ignore\n",
    "                break\n",
    "            bit = (num >> i) & 1\n",
    "            if bit:\n",
    "                if root.zero is not None and root.zero.count > 0:\n",
    "                    res |= 1 << i\n",
    "                    root = root.zero\n",
    "                else:\n",
    "                    root = root.one\n",
    "            else:\n",
    "                if root.one is not None and root.one.count > 0:\n",
    "                    res |= 1 << i\n",
    "                    root = root.one\n",
    "                else:\n",
    "                    root = root.zero\n",
    "\n",
    "        return res\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    class Solution:\n",
    "        def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "            trie = XorTrieSimple(max(nums))\n",
    "            res = 0\n",
    "            for num in nums:\n",
    "                trie.insert(num)\n",
    "                res = max(res, trie.query(num))\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        d = [set() for i in range(32)]\n",
    "        nums = set(nums)\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        if n == 1:\n",
    "            return ans\n",
    "\n",
    "        for num in nums:\n",
    "            i = 0\n",
    "            t = num\n",
    "            while t:\n",
    "                if t%2:\n",
    "                    d[i].add(num)\n",
    "                i += 1\n",
    "                t >>= 1\n",
    "        \n",
    "        while d and (len(d[-1]) == 0 or len(d[-1]) == n):\n",
    "            d.pop()\n",
    "\n",
    "        d1 = d.pop()\n",
    "        d0 = nums - d1\n",
    "        prob = [[d0, d1]]\n",
    "        ans += 2**(len(d))\n",
    "        \n",
    "        while d and prob:\n",
    "            # print(prob)\n",
    "            one = d.pop()\n",
    "            zero = nums - one\n",
    "            if not one or not zero:\n",
    "                continue\n",
    "            new = []\n",
    "            for d0, d1 in prob:\n",
    "                if one&d1 and zero&d0:\n",
    "                    new.append([zero&d0, one&d1])\n",
    "                if one&d0 and zero&d1:\n",
    "                    new.append([zero&d1, one&d0])\n",
    "            if new:\n",
    "                ans += 2**(len(d))\n",
    "                prob = new\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        import math\n",
    "        a = max(nums)\n",
    "        if a == 0:\n",
    "            return  0\n",
    "        bignumber = int(math.log2(a))\n",
    "        sorttree = {}\n",
    "        for i in range(len(nums)):\n",
    "            judge = pow(2,bignumber)\n",
    "            compare = nums[i]\n",
    "            tag = 0\n",
    "            for x in range(bignumber+1):\n",
    "                if compare//judge == 0:\n",
    "                    tag = 2*tag+1\n",
    "                    sorttree[tag] = nums[i]\n",
    "                else:\n",
    "                    tag = 2*tag+2\n",
    "                    sorttree[tag] = nums[i]\n",
    "                    compare = compare%judge\n",
    "                judge = judge/2\n",
    "        ans = 0\n",
    "        for j in range(len(nums)):\n",
    "            truejudge = pow(2,bignumber)\n",
    "            truecompare = nums[j]\n",
    "            truetag = 0\n",
    "            for k in range(bignumber+1):\n",
    "                if truecompare//truejudge == 0:\n",
    "                    if 2*truetag+2 not in sorttree:\n",
    "                        truetag = 2*truetag + 1\n",
    "                    else:\n",
    "                        truetag = 2*truetag + 2\n",
    "                else:\n",
    "                    if 2*truetag+1 not in sorttree:\n",
    "                        truetag = 2*truetag + 2\n",
    "                    else:\n",
    "                        truetag = 2*truetag + 1\n",
    "                    truecompare = truecompare%truejudge\n",
    "                truejudge = truejudge/2\n",
    "            ans = max(ans,sorttree[truetag]^nums[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "    from time import time\n",
    "    # create a binary tree, then search the top&long symmetry path\n",
    "    i = max(nums)\n",
    "    if not i: # i=0 leads k be -1, not desired 0 as i=1.\n",
    "      return 0\n",
    "    k = -1\n",
    "    while i:\n",
    "      k += 1\n",
    "      i >>= 1\n",
    "    t, ik, t0 = [0, 0], 1<<k, time()\n",
    "    for v in nums:\n",
    "      p, i = t, ik\n",
    "      for _ in range(k):\n",
    "        j = 1 if v&i else 0\n",
    "        if not p[j]:\n",
    "          p[j] = [0, 0]\n",
    "        p = p[j]\n",
    "        i >>= 1\n",
    "      p[v&1] = 1 # leaf layer not use [0,0] which cost some memory.\n",
    "    t1 = time()\n",
    "    #print(t)\n",
    "\n",
    "    def sym(k, l, r):\n",
    "      if not k:\n",
    "        return 0 # leaf layer has no child\n",
    "      #print(k, *l, '--', *r)\n",
    "      k -= 1\n",
    "      match( (8 if l[0] else 0) | (4 if l[1] else 0) | \n",
    "             (2 if r[0] else 0) | (1 if r[1] else 0) ):\n",
    "        case 0b1111:\n",
    "          return (1<<k) | max(sym(k, l[0], r[1]), sym(k, l[1], r[0]))\n",
    "        case 0b1001 | 0b1101 | 0b1011:\n",
    "          return (1<<k) | sym(k, l[0], r[1])\n",
    "        case 0b0110 | 0b1110 | 0b0111:\n",
    "          return (1<<k) | sym(k, l[1], r[0])\n",
    "        case 0b1010:\n",
    "          return sym(k, l[0], r[0])\n",
    "        case 0b0101:\n",
    "          return sym(k, l[1], r[1])\n",
    "        case _:  # bb00/00bb, 7 in total. should not be here.\n",
    "          print('bb00/00bb')\n",
    "\n",
    "    res = sym(k+1, t, t) # root need special treatment\n",
    "    t2 = time()\n",
    "    if t2 - t0 > 0.3:\n",
    "      print('%.3f %.3f'%(t1 - t0, t2 - t1))\n",
    "    return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryTrie:\n",
    "    \"\"\"\n",
    "    Reference:\n",
    "     - https://atcoder.jp/contests/arc028/submissions/19916627\n",
    "     - https://judge.yosupo.jp/submission/35057\n",
    "    \"\"\"\n",
    "\n",
    "    __slots__ = (\n",
    "        \"max_log\",\n",
    "        \"x_end\",\n",
    "        \"v_list\",\n",
    "        \"multiset\",\n",
    "        \"add_query_count\",\n",
    "        \"add_query_limit\",\n",
    "        \"edges\",\n",
    "        \"size\",\n",
    "        \"is_end\",\n",
    "        \"max_v\",\n",
    "        \"lazy\",\n",
    "    )\n",
    "\n",
    "    def __init__(\n",
    "        self,\n",
    "        max_log=31,\n",
    "        allow_multiple_elements=True,\n",
    "        add_query_limit=10**6,\n",
    "    ):\n",
    "        self.max_log = max_log\n",
    "        self.x_end = 1 << max_log\n",
    "        self.v_list = [0] * (max_log + 1)\n",
    "        self.multiset = allow_multiple_elements\n",
    "        self.add_query_count = 0\n",
    "        self.add_query_limit = add_query_limit\n",
    "        n = max_log * add_query_limit + 1\n",
    "        self.edges = [-1] * (2 * n)\n",
    "        self.size = [0] * n\n",
    "        self.is_end = [0] * n\n",
    "        self.max_v = 0\n",
    "        self.lazy = 0\n",
    "\n",
    "    def add(self, x: int):\n",
    "        # assert 0 <= x < self.x_end\n",
    "        # assert 0 <= self.add_query_count < self.add_query_limit\n",
    "        x ^= self.lazy\n",
    "        v = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            d = (x >> i) % 2\n",
    "            if self.edges[2 * v + d] == -1:\n",
    "                self.max_v += 1\n",
    "                self.edges[2 * v + d] = self.max_v\n",
    "            v = self.edges[2 * v + d]\n",
    "            self.v_list[i] = v\n",
    "        if self.multiset or self.is_end[v] == 0:\n",
    "            self.is_end[v] += 1\n",
    "            for v in self.v_list:\n",
    "                self.size[v] += 1\n",
    "        self.add_query_count += 1\n",
    "\n",
    "    def discard(self, x: int):\n",
    "        if not 0 <= x < self.x_end:\n",
    "            return\n",
    "        x ^= self.lazy\n",
    "        v = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            d = (x >> i) % 2\n",
    "            if self.edges[2 * v + d] == -1:\n",
    "                return\n",
    "            v = self.edges[2 * v + d]\n",
    "            self.v_list[i] = v\n",
    "        if self.is_end[v] > 0:\n",
    "            self.is_end[v] -= 1\n",
    "            for v in self.v_list:\n",
    "                self.size[v] -= 1\n",
    "\n",
    "    def erase(self, x: int, count: int = -1):\n",
    "        \"\"\"删除count个x x=-1表示删除所有x\"\"\"\n",
    "        # assert -1 <= count\n",
    "        if not 0 <= x < self.x_end:\n",
    "            return\n",
    "        x ^= self.lazy\n",
    "        v = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            d = (x >> i) % 2\n",
    "            if self.edges[2 * v + d] == -1:\n",
    "                return\n",
    "            v = self.edges[2 * v + d]\n",
    "            self.v_list[i] = v\n",
    "        if count == -1 or self.is_end[v] < count:\n",
    "            count = self.is_end[v]\n",
    "        if self.is_end[v] > 0:\n",
    "            self.is_end[v] -= count\n",
    "            for v in self.v_list:\n",
    "                self.size[v] -= count\n",
    "\n",
    "    def count(self, x: int) -> int:\n",
    "        if not 0 <= x < self.x_end:\n",
    "            return 0\n",
    "        x ^= self.lazy\n",
    "        v = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            d = (x >> i) % 2\n",
    "            if self.edges[2 * v + d] == -1:\n",
    "                return 0\n",
    "            v = self.edges[2 * v + d]\n",
    "        return self.is_end[v]\n",
    "\n",
    "    def bisect_left(self, x: int) -> int:\n",
    "        if x < 0:\n",
    "            return 0\n",
    "        if self.x_end <= x:\n",
    "            return len(self)\n",
    "        v = 0\n",
    "        ret = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            d = (x >> i) % 2\n",
    "            l = (self.lazy >> i) % 2\n",
    "            lc = self.edges[2 * v]\n",
    "            rc = self.edges[2 * v + 1]\n",
    "            if l == 1:\n",
    "                lc, rc = rc, lc\n",
    "            if d:\n",
    "                if lc != -1:\n",
    "                    ret += self.size[lc]\n",
    "                if rc == -1:\n",
    "                    return ret\n",
    "                v = rc\n",
    "            else:\n",
    "                if lc == -1:\n",
    "                    return ret\n",
    "                v = lc\n",
    "        return ret\n",
    "\n",
    "    def bisect_right(self, x: int) -> int:\n",
    "        return self.bisect_left(x + 1)\n",
    "\n",
    "    def index(self, x: int) -> int:\n",
    "        if x not in self:\n",
    "            raise ValueError(f\"{x} is not in BinaryTrie\")\n",
    "        return self.bisect_left(x)\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if x not in self:\n",
    "            return -1\n",
    "        return self.bisect_left(x)\n",
    "\n",
    "    def kth_elem(self, k: int) -> int:\n",
    "        if k < 0:\n",
    "            k += self.size[0]\n",
    "        # assert 0 <= k < self.size[0]\n",
    "        v = 0\n",
    "        ret = 0\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            l = (self.lazy >> i) % 2\n",
    "            lc = self.edges[2 * v]\n",
    "            rc = self.edges[2 * v + 1]\n",
    "            if l == 1:\n",
    "                lc, rc = rc, lc\n",
    "            if lc == -1:\n",
    "                v = rc\n",
    "                ret |= 1 << i\n",
    "                continue\n",
    "            if self.size[lc] <= k:\n",
    "                k -= self.size[lc]\n",
    "                v = rc\n",
    "                ret |= 1 << i\n",
    "            else:\n",
    "                v = lc\n",
    "        return ret\n",
    "\n",
    "    def minimum(self) -> int:\n",
    "        if self.size[0] == 0:\n",
    "            return 1 << self.max_log\n",
    "        return self.kth_elem(0)\n",
    "\n",
    "    def maximum(self) -> int:\n",
    "        if self.size[0] == 0:\n",
    "            return - (1 << self.max_log)\n",
    "        return self.kth_elem(-1)\n",
    "\n",
    "    def xor_all(self, x: int):\n",
    "        # assert 0 <= x < self.x_end\n",
    "        self.lazy ^= x\n",
    "\n",
    "    def __iter__(self):\n",
    "        q = [(0, 0)]\n",
    "        for i in range(self.max_log - 1, -1, -1):\n",
    "            l = (self.lazy >> i) % 2\n",
    "            nq = []\n",
    "            for v, x in q:\n",
    "                lc = self.edges[2 * v]\n",
    "                rc = self.edges[2 * v + 1]\n",
    "                if l == 1:\n",
    "                    lc, rc = rc, lc\n",
    "                if lc != -1:\n",
    "                    nq.append((lc, 2 * x))\n",
    "                if rc != -1:\n",
    "                    nq.append((rc, 2 * x + 1))\n",
    "            q = nq\n",
    "        for v, x in q:\n",
    "            for _ in range(self.is_end[v]):\n",
    "                yield x\n",
    "\n",
    "    def __str__(self):\n",
    "        prefix = \"BinaryTrie(\"\n",
    "        content = list(map(str, self))\n",
    "        suffix = \")\"\n",
    "        if content:\n",
    "            content[0] = prefix + content[0]\n",
    "            content[-1] = content[-1] + suffix\n",
    "        else:\n",
    "            content = [prefix + suffix]\n",
    "        return \", \".join(content)\n",
    "\n",
    "    def __getitem__(self, k):\n",
    "        return self.kth_elem(k)\n",
    "\n",
    "    def __contains__(self, x: int) -> bool:\n",
    "        return not not self.count(x)\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size[0]\n",
    "\n",
    "    def __bool__(self):\n",
    "        return not not len(self)\n",
    "\n",
    "    def __ixor__(self, x: int):\n",
    "        self.xor_all(x)\n",
    "        return self\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, A: List[int]) -> int:\n",
    "        bt = BinaryTrie(31, False, len(A))\n",
    "        res = -1\n",
    "        for x in A:\n",
    "            bt.add(x)\n",
    "            bt ^= x\n",
    "            res = max(res, bt.maximum())\n",
    "            # print(x, bt.maximum(), res)\n",
    "            # print(x, [y for y in bt], bt.minimum(), bt.maximum())\n",
    "            bt ^= x\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        def insert(num):\n",
    "            node = trie\n",
    "            for i in range(31, -1, -1):\n",
    "                val = (num >> i) & 1\n",
    "                if node[val] is None:\n",
    "                    node[val] = [None] * 2\n",
    "                node = node[val]\n",
    "        \n",
    "        def helper(num):\n",
    "            node, ans = trie, 0\n",
    "            for i in range(31, -1, -1):\n",
    "                val = (num >> i) & 1\n",
    "                if node[1 - val] is not None:\n",
    "                    ans = (ans << 1) + 1\n",
    "                    node = node[1 - val]\n",
    "                else:\n",
    "                    ans <<= 1\n",
    "                    node = node[val]\n",
    "            return ans\n",
    "\n",
    "        trie = [None] * 2\n",
    "        for num in nums:\n",
    "            insert(num)\n",
    "        return max(helper(num) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, nums):\n",
    "        self.tree = [None] * 2\n",
    "        for num in nums:\n",
    "            node = self.tree\n",
    "            for i in range(30, -1, -1):\n",
    "                v = num >> i & 1\n",
    "                if not node[v]:\n",
    "                    node[v] = [None] * 2\n",
    "                node = node[v]\n",
    "\n",
    "    def search(self, x):\n",
    "        node = self.tree\n",
    "        ans = 0\n",
    "        for i in range(30, -1, -1):\n",
    "            if not node:\n",
    "                return ans\n",
    "            v = x >> i & 1\n",
    "            ans <<= 1\n",
    "            if node[v ^ 1]:\n",
    "                ans += 1\n",
    "                node = node[v ^ 1]\n",
    "            else:\n",
    "                node = node[v]\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        trie = Trie(nums)\n",
    "        return max(trie.search(num) for num in nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        def add_node(s, root):\n",
    "            node = root\n",
    "            for ch in s:\n",
    "                x = int(ch)\n",
    "                if not node[x]:\n",
    "                    node[x] = [None, None]\n",
    "                node = node[x]\n",
    "\n",
    "        def max_xor(s, root):\n",
    "            node = root\n",
    "            ans = 0\n",
    "            for ch in s:\n",
    "                x = int(ch)\n",
    "                ans <<= 1\n",
    "                if node[1 - x]:\n",
    "                    ans += 1\n",
    "                    node = node[1 - x]\n",
    "                else:\n",
    "                    node = node[x]\n",
    "            return ans\n",
    "\n",
    "        root = [None, None]\n",
    "        num_b = ['{:0>32b}'.format(num) for num in nums]\n",
    "        ans = 0\n",
    "        for s in num_b:\n",
    "            add_node(s, root)\n",
    "            ans = max(ans, max_xor(s, root))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        L = 31\n",
    "        n = len(nums)\n",
    "        c = [Counter() for _ in range(L)]\n",
    "        for v in nums:\n",
    "            cur = 0\n",
    "            for j in range(L-1, -1, -1):\n",
    "                cur <<= 1\n",
    "                cur |= (v >> j) & 1\n",
    "                c[j][cur] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for v in nums:\n",
    "            cur = 0\n",
    "            for j in range(L-1, -1, -1):\n",
    "                cur <<= 1\n",
    "                cur |= ((v >> j) & 1) ^ 1\n",
    "                if cur not in c[j]:\n",
    "                    cur ^= 1\n",
    "            ans = max(ans, cur ^ v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self, n, mx) -> None:\n",
    "        '''\n",
    "        n: 数组长度\n",
    "        mx: 最大值\n",
    "        '''\n",
    "        self.n = n\n",
    "        self.mx = mx + 1\n",
    "        self.k = self.mx.bit_length()\n",
    "        self.LEN = self.n * self.k + 1\n",
    "\n",
    "        self.zero_side = [-1 for _ in range(self.LEN)]\n",
    "        self.one_side = [-1 for _ in range(self.LEN)]\n",
    "        self.counts = [0 for _ in range(self.LEN)]\n",
    "        self.nxt_node = 1\n",
    "    \n",
    "    def insert(self, num):\n",
    "        node = 0\n",
    "        for i in range(self.k - 1, -1, -1):\n",
    "            self.counts[node] += 1\n",
    "            if num >> i & 1:\n",
    "                if self.one_side[node] == -1:\n",
    "                    self.one_side[node] = self.nxt_node\n",
    "                    self.nxt_node += 1\n",
    "                node = self.one_side[node]\n",
    "            else:\n",
    "                if self.zero_side[node] == -1:\n",
    "                    self.zero_side[node] = self.nxt_node\n",
    "                    self.nxt_node += 1\n",
    "                node = self.zero_side[node]\n",
    "        self.counts[node] += 1\n",
    "    \n",
    "    def delete(self, num):\n",
    "        node = 0\n",
    "        for i in range(self.k - 1, -1, -1):\n",
    "            self.counts[node] -= 1\n",
    "            if num >> i & 1:\n",
    "                node = self.one_side[node]\n",
    "            else:\n",
    "                node = self.zero_side[node]\n",
    "    \n",
    "    def findMaxXor(self, v):\n",
    "        node = 0\n",
    "        res = 0\n",
    "        for i in range(self.k - 1, -1, -1):\n",
    "            if v >> i & 1:\n",
    "                if self.zero_side[node] != -1 and self.counts[self.zero_side[node]]:\n",
    "                    node = self.zero_side[node]\n",
    "                    res |= 1 << i\n",
    "                else:\n",
    "                    node = self.one_side[node]\n",
    "            else:\n",
    "                if self.one_side[node] != -1 and self.counts[self.one_side[node]]:\n",
    "                    node = self.one_side[node]\n",
    "                    res |= 1 << i\n",
    "                else:\n",
    "                    node = self.zero_side[node]\n",
    "        return res\n",
    "\n",
    "    def findMinXor(self, v):\n",
    "        node = 0\n",
    "        res = 0\n",
    "        for i in range(self.k - 1, -1, -1):\n",
    "            if v >> i & 1:\n",
    "                if self.one_side[node] and self.counts[self.one_side[node]]:\n",
    "                    node = self.one_side[node]\n",
    "                else:\n",
    "                    node = self.one_side[node]\n",
    "                    res |= 1 << i\n",
    "            else:\n",
    "                if self.zero_side[node] and self.counts[self.zero_side[node]]:\n",
    "                    node = self.zero_side[node]\n",
    "                else:\n",
    "                    node = self.zero_side[node]\n",
    "                    res |= 1 << i\n",
    "    \n",
    "    def countXorLessThan(self, num, limit):\n",
    "        node = 0\n",
    "        count = 0\n",
    "        for i in range(self.k - 1, -1, -1):\n",
    "            bitVal = (num >> i) & 1\n",
    "            limitBit = (limit >> i) & 1\n",
    "            if limitBit:\n",
    "                if self.zero_side[node] != -1:\n",
    "                    count += self.counts[self.zero_side[node]]\n",
    "                node = self.one_side[node] if bitVal == 0 else self.zero_side[node]\n",
    "            else:\n",
    "                node = self.zero_side[node] if bitVal == 0 else self.one_side[node]\n",
    "            if node == -1:\n",
    "                break\n",
    "        return count\n",
    "\n",
    "    def countXorLessThanEqual(self, num, limit):\n",
    "        return self.countXorLessThan(num, limit + 1)\n",
    "\n",
    "    def countXorGreaterThan(self, num, limit):\n",
    "        total = self.counts[0]\n",
    "        return total - self.countXorLessThanEqual(num, limit)\n",
    "\n",
    "    def countXorGreaterThanEqual(self, num, limit):\n",
    "        total = self.counts[0]\n",
    "        return total - self.countXorLessThan(num, limit)\n",
    "    \n",
    "    \n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        T = Trie(n, max(nums))\n",
    "        T.insert(nums[0])\n",
    "        res = 0\n",
    "\n",
    "        for num in nums[1:]:\n",
    "            res = max(res, T.findMaxXor(num))\n",
    "            print(num, T.findMaxXor(num))\n",
    "            T.insert(num)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        tr=[None,None,0]\n",
    "        def insert(x):\n",
    "            now=tr\n",
    "            for i in range(32,-1,-1):\n",
    "                v=x&(1<<i)\n",
    "                v=1 if v else 0\n",
    "                if now[v] is None:\n",
    "                    now[v]=[None,None,0]\n",
    "                now=now[v]\n",
    "            now[2]=x\n",
    "        def query(x):\n",
    "            now=tr\n",
    "            for i in range(32,-1,-1):\n",
    "                v=x&(1<<i)\n",
    "                v=1 if v else 0 \n",
    "                if now[1-v]:\n",
    "                    now=now[1-v]\n",
    "                else:\n",
    "                    now=now[v]\n",
    "            return x^now[2]\n",
    "        a=list(set(nums))\n",
    "        ans=0\n",
    "        for i in a:\n",
    "            insert(i)\n",
    "            now=query(i)\n",
    "            ans=max(now,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "XorTrie 最大异或前缀树\n",
    "https://kazuma8128.hatenablog.com/entry/2018/05/06/022654\n",
    "\"\"\"\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class BinaryTrie:\n",
    "    __slots__ = (\n",
    "        \"_maxLog\",\n",
    "        \"_xEnd\",\n",
    "        \"_vList\",\n",
    "        \"_multiset\",\n",
    "        \"_edges\",\n",
    "        \"_size\",\n",
    "        \"_endCount\",\n",
    "        \"_maxV\",\n",
    "        \"_lazy\",\n",
    "    )\n",
    "\n",
    "    def __init__(self, max=1 << 30, addLimit=int(2e5 + 10), allowMultipleElements=True):\n",
    "        \"\"\"\n",
    "        Example:\n",
    "\n",
    "        ```\n",
    "        n = len(nums)\n",
    "        bt = BinaryTrie(max = 1 << 30, addLimit=n, allowMultipleElements=True)\n",
    "        for num in nums:\n",
    "            bt.add(num)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            bt.xor_all(num)\n",
    "            res += bt.bisect_right(high) - bt.bisect_left(low)\n",
    "            bt.xor_all(num)\n",
    "        ```\n",
    "        \"\"\"\n",
    "        maxLog = max.bit_length()\n",
    "        self._maxLog = maxLog\n",
    "        self._xEnd = 1 << maxLog\n",
    "        self._vList = [0] * (maxLog + 1)\n",
    "        self._multiset = allowMultipleElements\n",
    "        n = maxLog * addLimit + 1\n",
    "        self._edges = [-1] * (2 * n)\n",
    "        self._size = [0] * n\n",
    "        self._endCount = [0] * n\n",
    "        self._maxV = 0\n",
    "        self._lazy = 0\n",
    "\n",
    "    def add(self, x: int) -> None:\n",
    "        x ^= self._lazy\n",
    "        v = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            d = (x >> i) & 1\n",
    "            if self._edges[2 * v + d] == -1:\n",
    "                self._maxV += 1\n",
    "                self._edges[2 * v + d] = self._maxV\n",
    "            v = self._edges[2 * v + d]\n",
    "            self._vList[i] = v\n",
    "        if self._multiset or self._endCount[v] == 0:\n",
    "            self._endCount[v] += 1\n",
    "            for v in self._vList:\n",
    "                self._size[v] += 1\n",
    "\n",
    "    def discard(self, x: int) -> None:\n",
    "        if not 0 <= x < self._xEnd:\n",
    "            return\n",
    "        x ^= self._lazy\n",
    "        v = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            d = (x >> i) & 1\n",
    "            if self._edges[2 * v + d] == -1:\n",
    "                return\n",
    "            v = self._edges[2 * v + d]\n",
    "            self._vList[i] = v\n",
    "        if self._endCount[v] > 0:\n",
    "            self._endCount[v] -= 1\n",
    "            for v in self._vList:\n",
    "                self._size[v] -= 1\n",
    "\n",
    "    def erase(self, x: int, count=1):\n",
    "        \"\"\"删除count个x.count=-1表示删除所有x.\"\"\"\n",
    "        if not 0 <= x < self._xEnd:\n",
    "            return\n",
    "        x ^= self._lazy\n",
    "        v = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            d = (x >> i) & 1\n",
    "            if self._edges[2 * v + d] == -1:\n",
    "                return\n",
    "            v = self._edges[2 * v + d]\n",
    "            self._vList[i] = v\n",
    "        if count == -1 or self._endCount[v] < count:\n",
    "            count = self._endCount[v]\n",
    "        if self._endCount[v] > 0:\n",
    "            self._endCount[v] -= count\n",
    "            for v in self._vList:\n",
    "                self._size[v] -= count\n",
    "\n",
    "    def count(self, x: int) -> int:\n",
    "        if not 0 <= x < self._xEnd:\n",
    "            return 0\n",
    "        x ^= self._lazy\n",
    "        v = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            d = (x >> i) & 1\n",
    "            if self._edges[2 * v + d] == -1:\n",
    "                return 0\n",
    "            v = self._edges[2 * v + d]\n",
    "        return self._endCount[v]\n",
    "\n",
    "    def bisectLeft(self, x: int) -> int:\n",
    "        if x < 0:\n",
    "            return 0\n",
    "        if self._xEnd <= x:\n",
    "            return len(self)\n",
    "        v = 0\n",
    "        ret = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            d = (x >> i) & 1\n",
    "            left = (self._lazy >> i) & 1\n",
    "            lc = self._edges[2 * v]\n",
    "            rc = self._edges[2 * v + 1]\n",
    "            if left == 1:\n",
    "                lc, rc = rc, lc\n",
    "            if d:\n",
    "                if lc != -1:\n",
    "                    ret += self._size[lc]\n",
    "                if rc == -1:\n",
    "                    return ret\n",
    "                v = rc\n",
    "            else:\n",
    "                if lc == -1:\n",
    "                    return ret\n",
    "                v = lc\n",
    "        return ret\n",
    "\n",
    "    def bisectRight(self, x: int) -> int:\n",
    "        return self.bisectLeft(x + 1)\n",
    "\n",
    "    def index(self, x: int) -> int:\n",
    "        if x not in self:\n",
    "            raise ValueError(f\"{x} is not in BinaryTrie\")\n",
    "        return self.bisectLeft(x)\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if x not in self:\n",
    "            return -1\n",
    "        return self.bisectLeft(x)\n",
    "\n",
    "    def at(self, index: int) -> int:\n",
    "        if index < 0:\n",
    "            index += self._size[0]\n",
    "        v = 0\n",
    "        ret = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            left = (self._lazy >> i) & 1\n",
    "            lc = self._edges[2 * v]\n",
    "            rc = self._edges[2 * v + 1]\n",
    "            if left == 1:\n",
    "                lc, rc = rc, lc\n",
    "            if lc == -1:\n",
    "                v = rc\n",
    "                ret |= 1 << i\n",
    "                continue\n",
    "            if self._size[lc] <= index:\n",
    "                index -= self._size[lc]\n",
    "                v = rc\n",
    "                ret |= 1 << i\n",
    "            else:\n",
    "                v = lc\n",
    "        return ret\n",
    "\n",
    "    def minimum(self) -> int:\n",
    "        return self.at(0)\n",
    "\n",
    "    def maximum(self) -> int:\n",
    "        return self.at(-1)\n",
    "\n",
    "    def xorAll(self, x: int) -> None:\n",
    "        self._lazy ^= x\n",
    "\n",
    "    def __iter__(self):\n",
    "        q = [(0, 0)]\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            left = (self._lazy >> i) & 1\n",
    "            nq = []\n",
    "            for v, x in q:\n",
    "                lc = self._edges[2 * v]\n",
    "                rc = self._edges[2 * v + 1]\n",
    "                if left == 1:\n",
    "                    lc, rc = rc, lc\n",
    "                if lc != -1:\n",
    "                    nq.append((lc, 2 * x))\n",
    "                if rc != -1:\n",
    "                    nq.append((rc, 2 * x + 1))\n",
    "            q = nq\n",
    "        for v, x in q:\n",
    "            for _ in range(self._endCount[v]):\n",
    "                yield x\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        prefix = \"BinaryTrie(\"\n",
    "        content = list(map(str, self))\n",
    "        suffix = \")\"\n",
    "        if content:\n",
    "            content[0] = prefix + content[0]\n",
    "            content[-1] = content[-1] + suffix\n",
    "        else:\n",
    "            content = [prefix + suffix]\n",
    "        return \", \".join(content)\n",
    "\n",
    "    def __getitem__(self, k: int) -> int:\n",
    "        return self.at(k)\n",
    "\n",
    "    def __contains__(self, x: int) -> bool:\n",
    "        return not not self.count(x)\n",
    "\n",
    "    def __len__(self) -> int:\n",
    "        return self._size[0]\n",
    "\n",
    "    def __bool__(self) -> bool:\n",
    "        return not not len(self)\n",
    "\n",
    "    def __ixor__(self, x: int) -> \"BinaryTrie\":\n",
    "        self.xorAll(x)\n",
    "        return self\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    class Solution:\n",
    "        def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "            trie = BinaryTrie(max=max(nums), addLimit=len(nums), allowMultipleElements=True)\n",
    "            res = 0\n",
    "            for num in nums:\n",
    "                trie.add(num)\n",
    "                trie.xorAll(num)\n",
    "                res = max(res, trie.maximum())\n",
    "                trie.xorAll(num)\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tree = [[None, None]]\n",
    "        def insert(x):\n",
    "            p = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                index = x >> i & 1\n",
    "                if not tree[p][index]:\n",
    "                    tree[p][index] = len(tree)\n",
    "                    tree.append([None, None])\n",
    "                p = tree[p][index]\n",
    "                \n",
    "        def query(x):\n",
    "            res = 0\n",
    "            p = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                index = x >> i & 1\n",
    "                if tree[p][int(not index)]:\n",
    "                    p = tree[p][int(not index)]\n",
    "                    res = (res << 1) | int(not index)\n",
    "                else:\n",
    "                    p = tree[p][index]\n",
    "                    res = (res << 1) | int(index)\n",
    "            return res\n",
    "        res = 0\n",
    "        for item in nums:\n",
    "            insert(item)\n",
    "            res = max(res, query(item) ^ item)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        ts = [[0, 0]]\n",
    "\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            bl = [0 for i in range(32)]\n",
    "            for i in range(32):\n",
    "                if num & (1 << i):\n",
    "                    bl[i] = 1\n",
    "            \n",
    "            now = 0\n",
    "            for i in range(31, -1, -1):\n",
    "                if ts[now][bl[i]] > 0:\n",
    "                    now = ts[now][bl[i]]\n",
    "                else:\n",
    "                    cnt = cnt + 1\n",
    "                    ts[now][bl[i]] = cnt \n",
    "                    ts.append([0, 0])\n",
    "                    now = cnt\n",
    "        \n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            bl = [0 for i in range(32)]\n",
    "            for i in range(32):\n",
    "                if num & (1 << i):\n",
    "                    bl[i] = 1\n",
    "\n",
    "            now = 0\n",
    "            ansnow = 0\n",
    "            for i in range(31, -1, -1):\n",
    "                if ts[now][1 - bl[i]] > 0:\n",
    "                    now = ts[now][1 - bl[i]]\n",
    "                    ansnow += (1 << i)\n",
    "                else:\n",
    "                    now = ts[now][bl[i]]\n",
    "            ans = max(ans, ansnow)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    __slots__ = (\"children\",)\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children: List[Trie | None] = [None, None]\n",
    "\n",
    "    def insert(self, x: int):\n",
    "        node = self\n",
    "        for i in range(30, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            if node.children[v] is None:\n",
    "                node.children[v] = Trie()\n",
    "            node = node.children[v]\n",
    "\n",
    "    def search(self, x: int) -> int:\n",
    "        node = self\n",
    "        ans = 0\n",
    "        for i in range(30, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            if node.children[v ^ 1]:\n",
    "                ans |= 1 << i\n",
    "                node = node.children[v ^ 1]\n",
    "            else:\n",
    "                node = node.children[v]\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        trie = Trie()\n",
    "        for x in nums:\n",
    "            trie.insert(x)\n",
    "        return max(trie.search(x) for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = (\"children\",)\n",
    "    def __init__(self):\n",
    "        self.children=[None,None]\n",
    "\n",
    "class Trie:\n",
    "    MX=30\n",
    "    def __init__(self):\n",
    "        self.root=Node()\n",
    "\n",
    "    def insert(self,val):\n",
    "        cur=self.root\n",
    "        for i in range(Trie.MX,-1,-1):\n",
    "            bit=(val>>i)&1\n",
    "            if cur.children[bit] is None:\n",
    "                cur.children[bit]=Node()\n",
    "            cur=cur.children[bit]\n",
    "\n",
    "    def max_xor(self,val:int):\n",
    "        cur=self.root\n",
    "        ans=0\n",
    "        for i in range(Trie.MX,-1,-1):\n",
    "            bit=(val>>i)&1\n",
    "            if cur.children[bit^1]:\n",
    "                ans|=1<<i  \n",
    "                bit^=1\n",
    "            cur=cur.children[bit]\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        t=Trie()\n",
    "        ans=0\n",
    "        for x in nums:\n",
    "            t.insert(x)\n",
    "            ans=max(ans,t.max_xor(x))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    High_BIT = 30\n",
    "    __slots__ = 'children'\n",
    "    def __init__(self):\n",
    "        self.children = [None,None]\n",
    "    def insert(self,val):\n",
    "        cur = self\n",
    "        for i in range(Trie.High_BIT,-1,-1):\n",
    "            bit = (val >> i) & 1\n",
    "            if not cur.children[bit]:\n",
    "                cur.children[bit] = Trie()\n",
    "            cur = cur.children[bit]\n",
    "    def query(self,val):\n",
    "        cur = self\n",
    "        ans = 0\n",
    "        for i in range(Trie.High_BIT,-1,-1):\n",
    "            bit = (val >> i) & 1\n",
    "            if cur.children[bit^1]:\n",
    "                ans |= (1 << i)\n",
    "                bit ^= 1\n",
    "            cur = cur.children[bit]\n",
    "        return ans\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        t = Trie()\n",
    "        ans = 0\n",
    "        for y in nums:\n",
    "            t.insert(y)\n",
    "            ans = max(ans,t.query(y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tire:\n",
    "    __slots__ = (\"child\",)\n",
    "\n",
    "    def __init__(self) -> None:\n",
    "        self.child = [None, None]\n",
    "\n",
    "    def insert(self, x) -> None:\n",
    "        t = self\n",
    "        for i in range(30, -1, -1):\n",
    "            c = ((x >> i) & 1)\n",
    "            if not t.child[c]:\n",
    "                t.child[c] = Tire()\n",
    "            t = t.child[c]\n",
    "    \n",
    "    def query(self, x) -> int:\n",
    "        res = 0\n",
    "        t = self\n",
    "        for i in range(30, -1, -1):\n",
    "            c = ((x >> i) & 1)\n",
    "            # p = c ^ 1 if t.child[c ^ 1] else c\n",
    "            # res |= (c ^ p) << i\n",
    "            # t = t.child[p]\n",
    "            if t.child[c ^ 1]:\n",
    "                res |= 1 << i\n",
    "                t = t.child[c ^ 1]\n",
    "            else:\n",
    "                t = t.child[c]\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        tire = Tire()\n",
    "        res = 0\n",
    "        for num in set(nums):\n",
    "            tire.insert(num)\n",
    "        return max(tire.query(x) for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    __slots__ = 'val', 'children'\n",
    "    def __init__(self, val=0):\n",
    "        self.val = val\n",
    "        self.children = [None, None]\n",
    "\n",
    "def insert(root, seq):\n",
    "    node = root\n",
    "    for i in seq:\n",
    "        i = int(i)\n",
    "        if not node.children[i]:\n",
    "            node.children[i] = TrieNode(i)\n",
    "        node = node.children[i]\n",
    "    node.children = []\n",
    "\n",
    "def query(root, seq):\n",
    "    ans = []\n",
    "    node = root\n",
    "    for i in seq:\n",
    "        i = int(i)\n",
    "        if node.children[1 - i]:\n",
    "            ans.append('1')\n",
    "            node = node.children[1 - i]\n",
    "        else:\n",
    "            ans.append('0')\n",
    "            node = node.children[i]\n",
    "    ans = ''.join(ans)\n",
    "    return int(ans, base=2)\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        mx = max(nums).bit_length()\n",
    "        seqs = []\n",
    "        root = TrieNode()\n",
    "        for n in nums:\n",
    "            n = bin(n)[2:]\n",
    "            pad = mx - len(n)\n",
    "            seqs.append('0' * pad + n)\n",
    "            insert(root, seqs[-1])\n",
    "        ans = 0\n",
    "        for s in seqs:\n",
    "            ret = query(root, s)\n",
    "            if ret > ans:\n",
    "                ans = ret\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    __slots__ = 'val', 'children'\n",
    "    def __init__(self, val=0):\n",
    "        self.val = val\n",
    "        self.children = [None, None]\n",
    "\n",
    "def insert(root, seq):\n",
    "    node = root\n",
    "    for i in seq:\n",
    "        i = int(i)\n",
    "        if not node.children[i]:\n",
    "            node.children[i] = TrieNode(i)\n",
    "        node = node.children[i]\n",
    "    node.children = []\n",
    "\n",
    "def query(root, seq):\n",
    "    ans = []\n",
    "    node = root\n",
    "    for i in seq:\n",
    "        i = int(i)\n",
    "        if node.children[1 - i]:\n",
    "            ans.append('1')\n",
    "            node = node.children[1 - i]\n",
    "        else:\n",
    "            ans.append('0')\n",
    "            node = node.children[i]\n",
    "    ans = ''.join(ans)\n",
    "    return int(ans, base=2)\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        seqs = []\n",
    "        root = TrieNode()\n",
    "        for n in nums:\n",
    "            n = bin(n)[2:]\n",
    "            pad = 32 - len(n)\n",
    "            seqs.append('0' * pad + n)\n",
    "            insert(root, seqs[-1])\n",
    "        ans = 0\n",
    "        for s in seqs:\n",
    "            ret = query(root, s)\n",
    "            if ret > ans:\n",
    "                ans = ret\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "def intBitNum(num: int) -> int:\n",
    "    bit = 0\n",
    "    while num > 0:\n",
    "        bit += 1\n",
    "        num >>= 1\n",
    "    return bit\n",
    "\n",
    "\n",
    "class BinTrie:\n",
    "    def __init__(self, capacity):\n",
    "        self.capacity = int(capacity)\n",
    "        self.trie = []\n",
    "        self.cnt = 1\n",
    "        self.maxbit = 31\n",
    "        for _ in range(self.capacity):\n",
    "            self.trie.append([0]*2)\n",
    "\n",
    "    def reset(self, maxbit):\n",
    "        self.cnt = 1\n",
    "        self.maxbit = maxbit\n",
    "        for i in range(self.capacity):\n",
    "            self.trie[i][0] = self.trie[i][1] = 0\n",
    "\n",
    "    def insert(self, num):\n",
    "        mask = 1 << (self.maxbit-1)\n",
    "        cur = 0\n",
    "        while mask > 0:\n",
    "            bit = 1 if num & mask else 0\n",
    "            mask = mask >> 1\n",
    "            nextnode = None if cur >= len(self.trie) else self.trie[cur]\n",
    "            if nextnode is None:\n",
    "                self.capacity += self.cnt\n",
    "                for _ in range(self.cnt):\n",
    "                    self.trie.append([0]*2)\n",
    "                nextnode = self.trie[cur]\n",
    "\n",
    "            if nextnode[bit] == 0:\n",
    "                nextnode[bit] = self.cnt\n",
    "                self.cnt += 1\n",
    "            cur = nextnode[bit]\n",
    "\n",
    "    def lookup(self, num: int) -> int:\n",
    "        mask = 1 << (self.maxbit-1)\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        while mask > 0:\n",
    "            bit = 1 if (num & mask) ^ mask else 0\n",
    "            mask = mask >> 1\n",
    "            nextnode = self.trie[cur]\n",
    "            if nextnode[bit] == 0:\n",
    "                bit = bit ^ 1\n",
    "            ans = (ans << 1) + bit\n",
    "            cur = nextnode[bit]\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self, cap=100) -> None:\n",
    "        self.trie = BinTrie(cap)\n",
    "\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        maxbit = intBitNum(max(nums))\n",
    "        self.trie.reset(maxbit)\n",
    "        for n in nums:\n",
    "            self.trie.insert(n)\n",
    "\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            ans = max(ans, n ^ self.trie.lookup(n))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        t = collections.defaultdict(lambda : [0, 0])\n",
    "        idx = 0\n",
    "        def add(x: int):\n",
    "            nonlocal idx\n",
    "            p = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                b = (x >> i) & 1\n",
    "                if not t[p][b]:\n",
    "                    idx += 1\n",
    "                    t[p][b] = idx\n",
    "\n",
    "                p = t[p][b]\n",
    "\n",
    "        def get(x: int) -> int:\n",
    "            p = 0\n",
    "            s = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                b = (x >> i) & 1\n",
    "                b ^= 1\n",
    "                if t[p][b]:\n",
    "                    s |= b << i\n",
    "                else:\n",
    "                    b ^= 1\n",
    "                    s |= b << i\n",
    "                p = t[p][b]\n",
    "\n",
    "            return s\n",
    "\n",
    "        ans = 0\n",
    "        for v in nums:\n",
    "            ans = max(ans, v ^ get(v))\n",
    "            add(v)\n",
    "       \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        son = {0: [0, 0]}\n",
    "        idx = 0\n",
    "        maxXorNum = 0\n",
    "        for x in nums:\n",
    "            p = pp = ret = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                u = (x >> i) & 1\n",
    "                if son[p][u] == 0:\n",
    "                    idx += 1\n",
    "                    son[idx] = [0, 0]\n",
    "                    son[p][u] = idx\n",
    "                p = son[p][u]\n",
    "\n",
    "                if son[pp][not u] != 0:  # 如果之前记录的数中的第 i 位有和 u 不一样的（异或，不一样才会是1）\n",
    "                    pp = son[pp][not u]\n",
    "                    if u == 0:\n",
    "                        ret |= 1 << i\n",
    "                else:\n",
    "                    pp = son[pp][u]\n",
    "                    if u == 1:\n",
    "                        ret |= 1 << i\n",
    "\n",
    "            t = ret ^ x\n",
    "            maxXorNum = t if t > maxXorNum else maxXorNum\n",
    "        return maxXorNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        root = [[],[]]\n",
    "        \n",
    "        def add(num):\n",
    "            node = root\n",
    "            bs = bin(num)[2:]\n",
    "            bs = (32 - len(bs)) * \"0\" + bs\n",
    "            for i in range(32):\n",
    "                if bs[i] == \"1\":\n",
    "                    if not node[1]:\n",
    "                        node[1] = [[], []]\n",
    "                    node = node[1]\n",
    "                else:\n",
    "                    if not node[0]:\n",
    "                        node[0] = [[], []]\n",
    "                    node = node[0]\n",
    "\n",
    "        @cache\n",
    "        def find(num):\n",
    "            res = 0\n",
    "            node = root\n",
    "            bs = bin(num)[2:]\n",
    "            bs = (32 - len(bs)) * \"0\" + bs\n",
    "            for i in range(32):\n",
    "                if bs[i] == \"1\":\n",
    "                    if node[0]:\n",
    "                        res += (1 << (31 - i))\n",
    "                        node = node[0]\n",
    "                    else:\n",
    "                        if node[1]:\n",
    "                            node = node[1]\n",
    "                        else:\n",
    "                            break\n",
    "                else:\n",
    "                    if node[1]:\n",
    "                        res += (1 << (31 - i))\n",
    "                        node = node[1]\n",
    "                    else:\n",
    "                        if node[0]:\n",
    "                            node = node[0]\n",
    "                        else:\n",
    "                            break\n",
    "            return res\n",
    "\n",
    "        ans = -inf\n",
    "        for num in nums:\n",
    "            ans = find(num) if find(num) > ans else ans\n",
    "            add(num)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        # 左子树指向表示 0 的子节点\n",
    "        self.left = None\n",
    "        # 右子树指向表示 1 的子节点\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        # 字典树的根节点\n",
    "        root = Trie()\n",
    "        # 最高位的二进制位编号为 30\n",
    "        HIGH_BIT = 30\n",
    "\n",
    "        def add(num: int):\n",
    "            cur = root\n",
    "            for k in range(HIGH_BIT, -1, -1):\n",
    "                bit = (num >> k) & 1\n",
    "                if bit == 0:\n",
    "                    if not cur.left:\n",
    "                        cur.left = Trie()\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    if not cur.right:\n",
    "                        cur.right = Trie()\n",
    "                    cur = cur.right\n",
    "\n",
    "        def check(num: int) -> int:\n",
    "            cur = root\n",
    "            x = 0\n",
    "            for k in range(HIGH_BIT, -1, -1):\n",
    "                bit = (num >> k) & 1\n",
    "                if bit == 0:\n",
    "                    # a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走\n",
    "                    if cur.right:\n",
    "                        cur = cur.right\n",
    "                        x = x * 2 + 1\n",
    "                    else:\n",
    "                        cur = cur.left\n",
    "                        x = x * 2\n",
    "                else:\n",
    "                    # a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走\n",
    "                    if cur.left:\n",
    "                        cur = cur.left\n",
    "                        x = x * 2 + 1\n",
    "                    else:\n",
    "                        cur = cur.right\n",
    "                        x = x * 2\n",
    "            return x\n",
    "\n",
    "        n = len(nums)\n",
    "        x = 0\n",
    "        for i in range(1, n):\n",
    "            # 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中\n",
    "            add(nums[i - 1])\n",
    "            # 将 nums[i] 看作 ai，找出最大的 x 更新答案\n",
    "            x = max(x, check(nums[i]))\n",
    "\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val = -1) -> None:\n",
    "        self.val = val\n",
    "        self.cnt = 1\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self) -> None:\n",
    "        self.root = Node()\n",
    "\n",
    "    def add(self, x: int, mx: int) -> None:\n",
    "        node = self.root\n",
    "        for i in range(mx - 1, -1, -1):\n",
    "            if (x >> i) & 1 == 0:\n",
    "                if node.left is None:\n",
    "                    node.left = Node(val = 0)\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    node = node.left\n",
    "                    node.cnt += 1\n",
    "            else:\n",
    "                if node.right is None:\n",
    "                    node.right = Node(val = 1)\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    node = node.right\n",
    "                    node.cnt += 1\n",
    "    \n",
    "    def max_xor(self, x: int, mx: int) -> int:\n",
    "        res = 0\n",
    "        node = self.root\n",
    "        for i in range(mx - 1, -1, -1):\n",
    "            if (x >> i) & 1 == 0:\n",
    "                if node.right is not None:\n",
    "                    res |= (1 << i)\n",
    "                    node = node.right\n",
    "                elif node.left is not None:\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    return res\n",
    "            else:\n",
    "                if node.left is not None:\n",
    "                    res |= (1 << i)\n",
    "                    node = node.left\n",
    "                elif node.right is not None:\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    return res\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        trie = Trie()\n",
    "        n = max(nums).bit_length()\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            ans = max(ans, trie.max_xor(x, n))\n",
    "            trie.add(x, n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        tree = TreeNode() \n",
    "        t = 0\n",
    "        for x in nums:\n",
    "            v = len(bin(x)) -2 \n",
    "            t = max(t,v) \n",
    "        g1 = []\n",
    "        g2 = [] \n",
    "        for x in nums:\n",
    "            v = len(bin(x)) -2 \n",
    "            if v<t:\n",
    "                g1.append(x)\n",
    "            else:\n",
    "                g2.append(x)\n",
    "        if len(g1)>len(g2):\n",
    "            g1, g2 = g2, g1 \n",
    "        for x in g1: \n",
    "            ss = self.mystr(x)\n",
    "            tree.insert(ss)\n",
    "        if len(g1)==0:\n",
    "            for x in g2: \n",
    "                ss = self.mystr(x)\n",
    "                tree.insert(ss)\n",
    "        rv = 0\n",
    "        for x in g2:\n",
    "            ss = self.mystr(x)\n",
    "            v = tree.search(ss)\n",
    "            rv = max(rv,v) \n",
    "        return rv \n",
    "\n",
    "    def mystr(self, v) -> str:\n",
    "        ss = bin(v)[2:]\n",
    "        ss = '0'*32 + ss \n",
    "        rv = ss[-32:]\n",
    "        return rv \n",
    "\n",
    "        \n",
    "\n",
    "class TreeNode:\n",
    "    '''\n",
    "    写一个二叉树\n",
    "    '''\n",
    "    def __init__(self, prefix=''):\n",
    "        self.prefix = prefix\n",
    "        self.left_prefix = prefix + '0'\n",
    "        self.right_prefix = prefix + '1'\n",
    "        self.left = None \n",
    "        self.right = None  \n",
    "\n",
    "    def insert(self, ss):\n",
    "        if self.prefix == ss:\n",
    "            return   \n",
    "        k = len(self.prefix)\n",
    "        v = ss[k]\n",
    "        if v=='0':\n",
    "            if self.left is None:\n",
    "                self.left = TreeNode(self.left_prefix)\n",
    "            self.left.insert(ss)\n",
    "        else:\n",
    "            if self.right is None:\n",
    "                self.right = TreeNode(self.right_prefix)\n",
    "            self.right.insert(ss)\n",
    "\n",
    "    def xor(self, ss) -> int:\n",
    "        x = int(self.prefix,2)\n",
    "        y = int(ss, 2)\n",
    "        rv = x ^ y \n",
    "        return rv \n",
    "    \n",
    "    def search(self, ss) -> int: \n",
    "        if len(self.prefix) == len(ss):\n",
    "            return self.xor(ss)\n",
    "        k = len(self.prefix)\n",
    "        v = ss[k]\n",
    "        if v=='0' and self.right is not None: \n",
    "            return self.right.search(ss)\n",
    "        if v=='1' and self.left is not None:\n",
    "            return self.left.search(ss)\n",
    "        if self.left is not None:\n",
    "            return self.left.search(ss)\n",
    "        if self.right is not None:\n",
    "            return self.right.search(ss)\n",
    "        return -1 \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.chd0 = None\n",
    "        self.chd1 = None\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumXOR(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        biggest = max(nums)\n",
    "        high = biggest.bit_length() - 1\n",
    "\n",
    "        trie = Trie()\n",
    "        mx = 0\n",
    "        for i in nums:\n",
    "            now = trie\n",
    "            for base in range(high, -1, -1):\n",
    "                key = i >> base & 1\n",
    "                if key == 0:\n",
    "                    if now.chd0 is None:\n",
    "                        now.chd0 = Trie()\n",
    "                    now = now.chd0\n",
    "                else:\n",
    "                    if now.chd1 is None:\n",
    "                        now.chd1 = Trie()\n",
    "                    now = now.chd1\n",
    "\n",
    "            val = 0\n",
    "            now = trie\n",
    "            for base in range(high, -1, -1):\n",
    "                key = i >> base & 1\n",
    "                if key == 0:\n",
    "                    if now.chd1 is None:\n",
    "                        now = now.chd0\n",
    "                        val = val << 1\n",
    "                    else:\n",
    "                        now = now.chd1\n",
    "                        val = (val << 1) | 1\n",
    "                else:\n",
    "                    if now.chd0 is None:\n",
    "                        now = now.chd1\n",
    "                        val = val << 1\n",
    "                    else:\n",
    "                        now = now.chd0\n",
    "                        val = (val << 1) | 1\n",
    "\n",
    "            if val > mx:\n",
    "                mx = val\n",
    "        return mx"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
